Header menu link for other important links
X
Returning and non-returning parallel communicating finite automata are equivalent
Ashish Choudhary, Kamala Krithivasan
Published in EDP Sciences
2007
Volume: 41
   
Issue: 2
Pages: 137 - 145
Abstract
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. © EDP Sciences 2007.
About the journal
JournalData powered by TypesetRAIRO - Theoretical Informatics and Applications
PublisherData powered by TypesetEDP Sciences
ISSN09883754
Open AccessYes
Concepts (7)
  •  related image
    Computational methods
  •  related image
    Formal languages
  •  related image
    Systems analysis
  •  related image
    Computational power
  •  related image
    MULTIHEAD FINITE AUTOMATON
  •  related image
    PARALLEL COMMUNICATING FINITE AUTOMATA SYSTEM
  •  related image
    Finite automata