FST TCS 2003: Foundations of Software Technology and Theoretical Computer Science

DOI10.1007/b94618zbMath1188.20066OpenAlexW2246750081MaRDI QIDQ5191514

Markus Lohrey, Volker Diekert

Publication date: 6 August 2009

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/b94618

zbMATH Keywords

algorithmsdecidabilitygraph productslogical theoriesequations in groupssolvability of equationsexistential theoriespositive theoriesequations in monoids

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Free semigroups, generators and relations, word problems (20M05) Undecidability and degrees of sets of sentences (03D35) Algebraic theory of languages and automata (68Q70) Decidability of theories and sets of sentences (03B25) Grammars and rewriting systems (68Q42) Free products of groups, free products with amalgamation, Higman-Neumann-Neumann extensions, and generalizations (20E06) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Algebraic geometry over groups; equations over groups (20F70)

Related Items

Existential questions in (relatively) hyperbolic groups. ⋮ Logical aspects of Cayley-graphs: the group case ⋮ The existential theory of equations with rational constraints in free groups is PSPACE-complete