The complexity of verbal languages over groups

DOI10.1016/J.JCSS.2018.10.005MaRDI QIDQ1713480zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Sanjay Jain, Frank Stephan, Alexei 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

Chomsky hierarchyfree groupspattern languagesautomatic groupsverbal 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)

Recommendations

• The complexity of verbal languages over groups
• scientific article; zbMATH DE number 2221698
• scientific article; zbMATH DE number 848082
• Learning pattern languages over groups
• scientific article

Cites work

• scientific article; zbMATH DE number 3841819 (Why is no real title available?)
• scientific article; zbMATH DE number 4031953 (Why is no real title available?)
• scientific article; zbMATH DE number 3660804 (Why is no real title available?)
• scientific article; zbMATH DE number 53661 (Why is no real title available?)
• scientific article; zbMATH DE number 3589737 (Why is no real title available?)
• scientific article; zbMATH DE number 2086419 (Why is no real title available?)
• scientific article; zbMATH DE number 3805807 (Why is no real title available?)
• scientific article; zbMATH DE number 806750 (Why is no real title available?)
• scientific article; zbMATH DE number 848082 (Why is no real title available?)
• scientific article; zbMATH DE number 3343706 (Why is no real title available?)
• A non-learnable class of E-pattern languages
• A relationship between ETOL and EDTOL languages
• Applications of L systems to group theory
• DECIDABILITY OF THE UNIVERSAL AND POSITIVE THEORIES OF A FREE GROUP
• Definable sets in a hyperbolic group.
• Elementary theory of free non-abelian groups.
• Extension of tabled 0L-systems and languages
• Finding patterns common to a set of strings
• From automatic structures to automatic groups.
• Generalized derivations with synchronized context-free grammars
• Generators and commutators in finite groups; abstract quotients of compact groups.
• Indexed Grammars—An Extension of Context-Free Grammars
• On rationality of verbal subsets in a group
• Regular patterns, regular languages and context-free languages
• Solution sets for equations over free groups are EDT0L languages
• THE PROBLEM OF SOLVABILITY OF EQUATIONS IN A FREE SEMIGROUP

Cited in

(6)

• Herzog–Schönheim conjecture, vanishing sums of roots of Unity and convex polygons
• scientific article; zbMATH DE number 1224049 (Why is no real title available?)
• The complexity of verbal languages over groups
• Formal Languages and Groups as Memory
• Verbal width in anabelian groups
• Groups, languages and dendric shifts

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1713480)