Returning and non-returning parallel communicating finite automata are equivalent
Dept of Computer Science and Engineering, Indian Institute of Technology,
Madras, Chennai, 600036 India;
2 Dept of Computer Science and Engineering, Indian Institute of Technology, Madras, Chennai, 600036 India; firstname.lastname@example.org
3 Faculty of Mathematics and Computer Science, University of Bucharest, Str. Academiei 14, 010014, Bucharest, Romania.
4 Research Group in Mathematical Linguistics, Rovira i Virgili University, Pl. Imperial Tarraco 1, 43005, Tarragona, Spain; email@example.com
Accepted: 30 March 2006
A parallel communicating automata system consists of several automata working independently in parallel and communicating with each other by request with the aim of recognizing a word. Rather surprisingly, returning parallel communicating finite automata systems are equivalent to the non-returning variants. We show this result by proving the equivalence of both with multihead finite automata. Some open problems are finally formulated.
Mathematics Subject Classification: 68Q45 / 68Q68
Key words: Formal languages / parallel communicating finite automata system / multihead finite automaton / computational power
© EDP Sciences, 2007