Multitape NFA: Weak Synchronization of the Input Heads

DOI10.1007/978-3-642-27660-6_20MaRDI QIDQ2891372zbMATH OpenOpenAlexFDO

Authors Ömer Eğecioğlu, Oscar H. Ibarra, Nicholas Q. Tran

Publication date 15 June 2012

Published in SOFSEM 2012: Theory and Practice of Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-27660-6_20

zbMATH Keywords

(un)decidabilitymultitape NFAweakly synchronized

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• On synchronized multi-tape and multi-head automata
• On Synchronized Multitape and Multihead Automata
• scientific article; zbMATH DE number 6665216
• How to synchronize the heads of a multitape automaton
• How to synchronize the heads of a multitape automaton
• Weak synchronization and synchronizability of multitape pushdown automata and Turing machines
• scientific article; zbMATH DE number 4143455
• Synchronizing non-deterministic finite automata
• Synchronization of Some DFA
• On multi-head automata with restricted nondeterminism

Cites work

• Bounded Algol-Like Languages
• On Context-Free Languages
• On Synchronized Multitape and Multihead Automata
• Relational string verification using multi-track automata
• Reversal-Bounded Multicounter Machines and Their Decision Problems
• Symbolic String Verification: Combining String Analysis and Size Analysis

Cited in

(5)

• On the open problem of Ginsburg concerning semilinear sets and related problems
• On the boundedness property of semilinear sets
• Weak synchronization and synchronizability of multitape pushdown automata and Turing machines
• scientific article; zbMATH DE number 6665216 (Why is no real title available?)
• On deciding synchronizability for asynchronously communicating systems

Describes a project that uses

Uses Software

• ALGOL 60

This page was built for publication: Multitape NFA: Weak Synchronization of the Input Heads

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