Existential and positive theories of equations in graph products

DOI10.1007/s00224-003-1110-xzbMath1067.03017OpenAlexW2090997504MaRDI QIDQ705067

Volker Diekert, Markus Lohrey

Publication date: 25 January 2005

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-003-1110-x

zbMATH Keywords

complexitydecidabilityfree groupsfree monoidsPSPACEtrace monoidgraph productexistential theorypositive theory

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Free semigroups, generators and relations, word problems (20M05) Decidability of theories and sets of sentences (03B25) Complexity of computation (including implicit computational complexity) (03D15) Grammars and rewriting systems (68Q42) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (8)

The Diophantine problem in some metabelian groups ⋮ WORD EQUATIONS OVER GRAPH PRODUCTS ⋮ Logical aspects of Cayley-graphs: the group case ⋮ Equations in groups that are virtually direct products ⋮ On systems of equations over free partially commutative groups ⋮ First-order aspects of Coxeter groups ⋮ The existential theory of equations with rational constraints in free groups is PSPACE-complete ⋮ SOLVABILITY OF EQUATIONS IN GRAPH GROUPS IS DECIDABLE

This page was built for publication: Existential and positive theories of equations in graph products