Equation satisfiability and program satisfiability for finite monoids

DOI10.1007/3-540-44612-5_13MaRDI QIDQ4536353zbMATH OpenFDO

Authors David Mix Barrington, Pierre McKenzie, Chris Moore, Pascal Tesson, Denis Thérien

Publication date 4 November 2002

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

Full work available at URL https://doi.org/10.1007/3-540-44612-5_13

Mathematics Subject Classification ID

Semigroups in automata theory, linguistics, etc. (20M35) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Algebraic theory of languages and automata (68Q70)

Recommendations

• Satisfiability of systems of equations over finite monoids
• Term equation satisfiability over finite algebras
• The complexity of solving equations over finite groups
• Dichotomies in the complexity of solving systems of equations over finite semigroups
• Alphabetical satisfiability problem for trace equations

Cited in

(14)

• The complexity of solving equations over finite groups
• Inapproximability results for equations over finite groups
• Solving a fixed number of equations over finite groups
• Learning expressions and programs over monoids
• Complexity issues of checking identities in finite monoids
• Learning expressions over monoids (extended abstract)
• Satisfiability of systems of equations over finite monoids
• Zero testing and equation solving for sparse polynomials on rectangular domains
• Equation satisfiability in solvable groups
• Hardness of equations over finite solvable groups under the exponential time hypothesis
• Membership and conjugacy in inverse semigroups
• Nonuniform deterministic finite automata over finite algebraic structures
• Groups with identities
• Inapproximability results for equations over infinite groups

This page was built for publication: Equation satisfiability and program satisfiability for finite monoids

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