Returning and non-returning parallel communicating finite automata are equivalent

DOI10.1051/ita:2007014zbMath1146.68385OpenAlexW2170950469MaRDI QIDQ5441543

Kamala Krithivasan, Victor Mitrana, Ashish Choudhury

Publication date: 15 February 2008

Published in: RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL: http://www.numdam.org/item?id=ITA_2007__41_2_137_0

zbMATH Keywords

multihead finite automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items

UNDECIDABILITY AND HIERARCHY RESULTS FOR PARALLEL COMMUNICATING FINITE AUTOMATA ⋮ ON THE COMPUTATIONAL CAPACITY OF PARALLEL COMMUNICATING FINITE AUTOMATA ⋮ Asynchronous Parallel Communicating Systems of Pushdown Automata ⋮ Complexity of multi-head finite automata: origins and directions ⋮ On the Computational Capacity of Parallel Communicating Finite Automata ⋮ Returning Parallel Communicating Finite Automata with Communication Bounds: Hierarchies, Decidabilities, and Undecidabilities ⋮ Reversible parallel communicating finite automata systems

Cites Work

• Unnamed Item
• Unnamed Item
• Multiprocessor automata
• Stack cooperation in multistack pushdown automata
• On non-determinacy in simple computing devices
• On two-way multihead automata
• PARALLEL FINITE AUTOMATA SYSTEMS COMMUNICATING BY STATES
• PARALLEL COMMUNICATING PUSHDOWN AUTOMATA SYSTEMS