Returning and non-returning parallel communicating finite automata are equivalent

被引：12

作者：

Choudhary, Ashish ^{[1
]}

Krithivasan, Kamala

Mitrana, Victor

机构：

[1] Indian Inst Technol, Dept Comp Sci & Engn, Madras 600036, Tamil Nadu, India

[2] Univ Bucharest, Fac Math & Comp Sci, Bucharest 010014, Romania

[3] Univ Rovira & Virgili, Res Grp Math Linguist, Tarragona 43005, Spain

来源：

RAIRO-THEORETICAL INFORMATICS AND APPLICATIONS | 2007年 / 41卷 / 02期

关键词：

formal languages; parallel communicating finite automata system; multihead finite automaton; computational power;

D O I：

10.1051/ita:2007014

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

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.

引用

页码：137 / 145

页数：9

共 9 条

[1] [Anonymous], 1997, Handbook of Formal Language Theory
[2] BUDA AO, 1977, INFORM PROCESS LETT, V25, P257
[3] Csuhaj-Varju E, 1994, GRAMMAR SYSTEMS GRAM
[4] CSUHAJVARJU E, 2000, INT J FOUND COMPUT S, V11, P633
[5] Stack cooperation in multistack pushdown automata
Dassow, J
Mitrana, V
[J]. JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1999, 58 (03) : 611 - 621
[6] DASSOW J, GRAMMAR SYSTEMS
[7] Hartmanis J., 1972, Acta Informatica, V1, P336, DOI 10.1007/BF00289513
[8] Ibarra O. H., 1973, Journal of Computer and System Sciences, V7, P28, DOI 10.1016/S0022-0000(73)80048-0
[9] Martin-Vide C., 2002, International Journal of Foundations of Computer Science, V13, P733, DOI 10.1142/S0129054102001424

← 1 →