Existential and positive theories of equations in graph products

DOI10.1007/S00224-003-1110-XzbMATH Open1067.03017OpenAlexW2090997504MaRDI QIDQ705067FDOQ705067

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

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

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)

Cited In (13)

• Logical aspects of Cayley-graphs: the group case
• Title not available (Why is that?)
• 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.
• Title not available (Why is that?)
• 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
• A NOTE ON THE EXISTENTIAL THEORY OF EQUATIONS IN PLAIN 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)