Existential and positive theories of equations in graph products

DOI10.1007/S00224-003-1110-XMaRDI QIDQ705067zbMATH OpenOpenAlexFDO

Authors 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 groupsPSPACEfree monoidstrace monoidgraph productexistential theorypositive theory

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 2086411
• On the generic existential theory of finite graphs
• Equational theory of relation algebras with positive operations
• The Equational Logic For Graph Algebras
• Graph products of completely positive maps
• scientific article; zbMATH DE number 1047921
• Equivalence proof for intuitionistic existential alpha graphs
• A note on equational theories
• On the equational graphs over finite fields
• Positive model theory and amalgamations

Cited in

(13)

• A NOTE ON THE EXISTENTIAL THEORY OF EQUATIONS IN PLAIN GROUPS
• Logical aspects of Cayley-graphs: the group case
• scientific article; zbMATH DE number 2086411 (Why is no real title available?)
• FST TCS 2003: Foundations of Software Technology and Theoretical Computer Science
• SOLVABILITY OF EQUATIONS IN GRAPH GROUPS IS DECIDABLE
• WORD EQUATIONS OVER GRAPH PRODUCTS
• On systems of equations over free partially commutative groups.
• scientific article; zbMATH DE number 1754619 (Why is no real title available?)
• First-order aspects of Coxeter groups
• Presburger arithmetic with stars, rational subsets of graph groups, and nested zero tests
• Equations in groups that are virtually direct products
• The existential theory of equations with rational constraints in free groups is PSPACE-complete
• The Diophantine problem in some metabelian groups

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q705067)