The complexity of verbal languages over groups

DOI10.1016/j.jcss.2018.10.005zbMath1412.68132WikidataQ59864149 ScholiaQ59864149MaRDI QIDQ1713480

Sanjay Jain, Frank Stephan, Alexei G. Myasnikov

Publication date: 25 January 2019

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2018.10.005

zbMATH Keywords

free groups; automatic groups; Chomsky hierarchy; pattern languages; verbal languages

Mathematics Subject Classification ID

68Q45: Formal languages and automata

68Q70: Algebraic theory of languages and automata

20F10: Word problems, other decision problems, connections with logic and automata (group-theoretic aspects)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Generators and commutators in finite groups; abstract quotients of compact groups.
• A non-learnable class of E-pattern languages
• Elementary theory of free non-abelian groups.
• Finding patterns common to a set of strings
• A relationship between ETOL and EDTOL languages
• Regular patterns, regular languages and context-free languages
• From automatic structures to automatic groups.
• On rationality of verbal subsets in a group
• Generalized Derivations with Synchronized Context-Free Grammars
• Solution Sets for Equations over Free Groups are EDT0L Languages
• DECIDABILITY OF THE UNIVERSAL AND POSITIVE THEORIES OF A FREE GROUP
• Extension of tabled 0L-systems and languages
• THE PROBLEM OF SOLVABILITY OF EQUATIONS IN A FREE SEMIGROUP
• Applications of L systems to group theory
• DEFINABLE SETS IN A HYPERBOLIC GROUP
• Indexed Grammars—An Extension of Context-Free Grammars