A Polynomial Time Algorithm for Deciding the Equivalence Problem for 2-Tape Deterministic Finite State Acceptors

DOI10.1137/0211013zbMath0497.68050OpenAlexW2066201500MaRDI QIDQ3962488

Sheila A. Greibach, Emily P. Friedman

Publication date: 1982

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

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

zbMATH Keywords

time complexitydepth-first searchmultitape automataRAM

Mathematics Subject Classification ID

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

Related Items

A note on finite-valued and finitely ambiguous transducers ⋮ Efficient Equivalence Checking Technique for Some Classes of Finite-State Machines ⋮ A polynomial algorithm testing partial confluence of basic semi-Thue systems ⋮ The complexity of decision problems for finite-turn multicounter machines ⋮ A polynomial algorithm testing partial confluence of basic semi-Thue systems ⋮ Transducing reversibly with finite state machines ⋮ \(L(A)=L(B)\)? decidability results from complete formal systems ⋮ An extended direct branching algorithm for checking equivalence of deterministic pushdown automata ⋮ Lambda-confluence for context rewriting systems

This page was built for publication: A Polynomial Time Algorithm for Deciding the Equivalence Problem for 2-Tape Deterministic Finite State Acceptors