scientific article; zbMATH DE number 1759404

MaRDI QIDQ4536353zbMATH OpenFDO

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

Publication date 4 November 2002

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

• scientific article; zbMATH DE number 1834675
• 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

(12)

• 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
• scientific article; zbMATH DE number 1688371 (Why is no real title available?)
• scientific article; zbMATH DE number 1834675 (Why is no real title available?)
• 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
• Groups with identities
• Inapproximability results for equations over infinite groups

This page was built for publication:

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