Context-Free Word Problem Semigroups

被引：6

作者：

Brough, Tara ^{[1
]}

Cain, Alan J. ^{[1
]}

Pfeiffer, Markus ^{[2
]}

机构：

[1] Univ Nova Lisboa, Ctr Matemat & Aplicacoes, Fac Ciencias & Tecnol, P-2829516 Caparica, Portugal

[2] Univ St Andrews, Sch Comp Sci, St Andrews KY16 9SS, Fife, Scotland

来源：

DEVELOPMENTS IN LANGUAGE THEORY, DLT 2019 | 2019年 / 11647卷

关键词：

D O I：

10.1007/978-3-030-24886-4_22

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

This paper studies the classes of semigoups and monoids with context-free and deterministic context-free word problem. First, some examples are exhibited to clarify the relationship between these classes and their connection with the notions of word-hyperbolicity and automaticity. Second, a study is made of whether these classes are closed under applying certain semigroup constructions, including direct products and free products, or under regressing from the results of such constructions to the original semigroup(s) or monoid(s).

引用

页码：292 / 305

页数：14

共 23 条

[1]

Book Ronald V., 1993, String-Rewriting Systems, DOI DOI 10.1007/978-1-4613-9771-7

[2]

Brough T., 2018, LANGUAGE HIERARCHY B

[3]

Brough T., 2010, THESIS U WARWICK

[4] Word Problem Languages for Free Inverse Monoids [J].

Brough, Tara .

DESCRIPTIONAL COMPLEXITY OF FORMAL SYSTEMS, DCFS 2018, 2018, 10952 :24-36

[5] Groups with poly-context-free word problem [J].

Brough, Tara .

GROUPS COMPLEXITY CRYPTOLOGY, 2014, 6 (01) :9-29

[6] CONTEXT-FREE REWRITING SYSTEMS AND WORD-HYPERBOLIC STRUCTURES WITH UNIQUENESS [J].

Cain, Alan J. ;

Maltcev, Victor .

INTERNATIONAL JOURNAL OF ALGEBRA AND COMPUTATION, 2012, 22 (07)

[7] Automatic semigroups [J].

Campbell, CM ;

Robertson, EF ;

Ruskuc, N ;

Thomas, RM .

THEORETICAL COMPUTER SCIENCE, 2001, 250 (1-2) :365-391

[8] Word hyperbolic semigroups [J].

Duncan, A ;

Gilman, RH .

MATHEMATICAL PROCEEDINGS OF THE CAMBRIDGE PHILOSOPHICAL SOCIETY, 2004, 136 :513-524

[9] THE ACCESSIBILITY OF FINITELY PRESENTED GROUPS [J].

DUNWOODY, MJ .

INVENTIONES MATHEMATICAE, 1985, 81 (03) :449-457

[10]

Epstein D.B.A., 1992, Word Processing in Groups

← 1 2 3 →