Solution Sets for Equations over Free Groups are EDT0L Languages

DOI10.1007/978-3-662-47666-6_11zbMath1412.68124arXiv1508.02149OpenAlexW2963535475MaRDI 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

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Semigroups in automata theory, linguistics, etc. (20M35) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Algebraic geometry over groups; equations over groups (20F70)

Related Items (8)

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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

This page was built for publication: Solution Sets for Equations over Free Groups are EDT0L Languages