Solution Sets for Equations over Free Groups are EDT0L Languages

DOI10.1007/978-3-662-47666-6_11zbMath1412.68124arXiv1508.02149MaRDI QIDQ3449471

Laura Ciobanu, Volker Diekert, Murray J. Elder

Publication date: 4 November 2015

Published in: Automata, Languages, and Programming (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1508.02149

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68Q45: Formal languages and automata

20M35: Semigroups in automata theory, linguistics, etc.

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

20F70: Algebraic geometry over groups; equations over groups

Related Items

Ideals of equations for elements in a free group and context-free languages, On groups generated by involutions of a semigroup., The complexity of verbal languages over groups, A language hierarchy of binary relations, A logic for document spanners, Equations over free inverse monoids with idempotent variables, Solution sets for equations over free groups are EDT0L languages, More Than 1700 Years of Word Equations

Cites Work

• Elementary theory of free non-abelian groups.
• Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
• Diophantine geometry over groups. VIII: Stability.
• Word-mappings of level 2
• An efficient algorithm for solving word equations
• The Complexity of Verbal Languages over Groups
• Controlled iteration grammars and full hyper-AFL's
• Finding All Solutions of Equations in Free Groups and Monoids with Involution
• Indexed Grammars—An Extension of Context-Free Grammars
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item