Polynomial algorithm for equivalence problem of deterministic multitape finite automata

DOI10.1016/j.tcs.2020.05.044zbMath1451.68149OpenAlexW3033311762MaRDI QIDQ784484

Samvel K. Shoukourian, Hayk A. Grigoryan

Publication date: 3 August 2020

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2020.05.044

zbMATH Keywords

equivalencepolynomial complexitydeterministic multitape finite automata

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Cites Work

• The equivalence problem for deterministic two-tape automata
• The equivalence problem of multitape finite automata
• The Equivalence Problem of Deterministic Multitape Finite Automata: A New Proof of Solvability Using a Multidimensional Tape
• Reducibility of program-scheme functional equivalence on a nondegenerate basis of rank unity to the equivalence of automata with multidimensional tapes
• Revisiting the Equivalence Problem for Finite Multitape Automata
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item