Dichotomies in the complexity of solving systems of equations over finite semigroups

DOI10.1007/s00224-005-1279-2zbMath1109.68051OpenAlexW1993202907MaRDI QIDQ870451

Denis Thérien, Pascal Tesson, Ondřej Klíma

Publication date: 12 March 2007

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

Full work available at URL: https://doi.org/10.1007/s00224-005-1279-2

zbMATH Keywords

satifiability problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Semigroups in automata theory, linguistics, etc. (20M35) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (8)

Loosely-abelian algebras ⋮ Towards breaking the exponential barrier for general secret sharing ⋮ Satisfiability in MultiValued Circuits ⋮ Identity checking problem for transformation monoids ⋮ Solving equation systems in ω-categorical algebras ⋮ Identity Problems, Solvability of Equations and Unification in Varieties of Semigroups Related to Varieties of Groups ⋮ Constraint Satisfaction Problems with Infinite Templates ⋮ The complexity of equivalence and isomorphism of systems of equations over finite groups

This page was built for publication: Dichotomies in the complexity of solving systems of equations over finite semigroups