The complexity of verbal languages over groups

DOI10.1016/J.JCSS.2018.10.005zbMath1412.68132DBLPjournals/jcss/JainMS19OpenAlexW2901968431WikidataQ59864149 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 groupsautomatic groupsChomsky hierarchypattern languagesverbal languages

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Algebraic theory of languages and automata (68Q70) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10)

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

This page was built for publication: The complexity of verbal languages over groups