Solution Sets for Equations over Free Groups are EDT0L Languages
From MaRDI portal
Publication:3449471
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
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