The Complexity of theA B CProblem

DOI10.1137/S0097539794276853zbMath0967.20029OpenAlexW1966167381MaRDI QIDQ4507329

Jin-Yi Cai, Richard J. Lipton, Yechezkel Zalcstein

Publication date: 18 October 2000

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0097539794276853

zbMATH Keywords

membership problempolynomial-time algorithmsJordan normal formscommutative linear semigroups

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Free semigroups, generators and relations, word problems (20M05) Matrix equations and identities (15A24) Algebraic systems of matrices (15A30)

Related Items (4)

Knapsack and the power word problem in solvable Baumslag–Solitar groups ⋮ Unnamed Item ⋮ REACHABILITY PROBLEMS FOR PRODUCTS OF MATRICES IN SEMIRINGS ⋮ Complete semialgebraic invariant synthesis for the Kannan-Lipton orbit problem

This page was built for publication: The Complexity of theA B CProblem