Weak Synchronization and Synchronizability of Multitape Pushdown Automata and Turing Machines

DOI10.1007/978-3-642-28332-1_29zbMath1351.68102OpenAlexW182536255MaRDI QIDQ2890204

Oscar H. Ibarra, Nicholas Q. Tran

Publication date: 8 June 2012

Published in: Language and Automata Theory and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-28332-1_29

zbMATH Keywords

halting problemPost correspondence problemreversal-bounded counters(un)decidabilitymultitape Turing machinesmultitape NPDAsweakly synchronized

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (2)

On the open problem of Ginsburg concerning semilinear sets and related problems ⋮ On the Boundedness Property of Semilinear Sets

This page was built for publication: Weak Synchronization and Synchronizability of Multitape Pushdown Automata and Turing Machines