Polynomial algorithm for equivalence problem of deterministic multitape finite automata

DOI10.1016/J.TCS.2020.05.044MaRDI QIDQ784484zbMATH OpenOpenAlexFDO

Authors Hayk Grigoryan, Samvel K. Shoukourian

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

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

Recommendations

• Algorithm for establishing the equivalence of deterministic multitape automata
• The Equivalence Problem of Deterministic Multitape Finite Automata: A New Proof of Solvability Using a Multidimensional Tape
• Revisiting the equivalence problem for finite multitape automata
• The equivalence problem of multidimensional multitape automata
• The equivalence problem of multitape finite automata

Cites work

• scientific article; zbMATH DE number 3168668 (Why is no real title available?)
• scientific article; zbMATH DE number 3972221 (Why is no real title available?)
• scientific article; zbMATH DE number 3179521 (Why is no real title available?)
• scientific article; zbMATH DE number 3254905 (Why is no real title available?)
• 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
• The Equivalence Problem of Deterministic Multitape Finite Automata: A New Proof of Solvability Using a Multidimensional Tape
• The equivalence problem for deterministic two-tape automata
• The equivalence problem of multitape finite automata

Cited in

(3)

• Polynomial inference of universal automata from membership and equivalence queries
• scientific article; zbMATH DE number 1948505 (Why is no real title available?)
• Algorithm for establishing the equivalence of deterministic multitape automata

This page was built for publication: Polynomial algorithm for equivalence problem of deterministic multitape finite automata

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