Real-Time Recognition of Cyclic Strings by One-Way and Two-Way Cellular Automata

Katsuhiko NAKAMURA

doi:10.1093/ietisy/e88-d.1.65

Real-Time Recognition of Cyclic Strings by One-Way and Two-Way Cellular Automata

Katsuhiko NAKAMURA

Full Text Views

0

Share
Cite this

Summary :

This paper discusses real-time language recognition by 1-dimensional one-way cellular automata (OCAs) and two-way cellular automata (CAs), focusing on limitations of the parallel computation power. To clarify the limitations, we investigate real-time recognition of cyclic strings of the form u^k with u {0,1}⁺ and k 2. We show a version of pumping lemma for recognizing cyclic strings by OCAs, which can be used for proving that several languages are not recognizable by OCAs in real time. The paper also discusses the real-time language recognition of CAs by prefix and postfix computation, in which every prefix or postfix of an input string is also accepted, if the prefix or postfix is in the language. It is shown that there are languages L Σ⁺ such that L is not recognizable by OCA in real-time and the reversal of L and the concatenation LΣ^* are recognizable by CA in real-time.

Publication: IEICE TRANSACTIONS on Information Vol.E88-D No.1 pp.65-71

Publication Date: 2005/01/01

Publicized

Online ISSN

DOI: 10.1093/ietisy/e88-d.1.65

Type of Manuscript: Special Section PAPER (Special Section on Foundations of Computer Science)

Category

Cite this

Copy

Katsuhiko NAKAMURA, "Real-Time Recognition of Cyclic Strings by One-Way and Two-Way Cellular Automata" in IEICE TRANSACTIONS on Information, vol. E88-D, no. 1, pp. 65-71, January 2005, doi: 10.1093/ietisy/e88-d.1.65.
Abstract: This paper discusses real-time language recognition by 1-dimensional one-way cellular automata (OCAs) and two-way cellular automata (CAs), focusing on limitations of the parallel computation power. To clarify the limitations, we investigate real-time recognition of cyclic strings of the form u^k with u {0,1}⁺ and k 2. We show a version of pumping lemma for recognizing cyclic strings by OCAs, which can be used for proving that several languages are not recognizable by OCAs in real time. The paper also discusses the real-time language recognition of CAs by prefix and postfix computation, in which every prefix or postfix of an input string is also accepted, if the prefix or postfix is in the language. It is shown that there are languages L Σ⁺ such that L is not recognizable by OCA in real-time and the reversal of L and the concatenation LΣ^* are recognizable by CA in real-time.
URL: https://globals.ieice.org/en_transactions/information/10.1093/ietisy/e88-d.1.65/_p

Copy

@ARTICLE{e88-d_1_65,
author={Katsuhiko NAKAMURA, },
journal={IEICE TRANSACTIONS on Information},
title={Real-Time Recognition of Cyclic Strings by One-Way and Two-Way Cellular Automata},
year={2005},
volume={E88-D},
number={1},
pages={65-71},
abstract={This paper discusses real-time language recognition by 1-dimensional one-way cellular automata (OCAs) and two-way cellular automata (CAs), focusing on limitations of the parallel computation power. To clarify the limitations, we investigate real-time recognition of cyclic strings of the form u^k with u {0,1}⁺ and k 2. We show a version of pumping lemma for recognizing cyclic strings by OCAs, which can be used for proving that several languages are not recognizable by OCAs in real time. The paper also discusses the real-time language recognition of CAs by prefix and postfix computation, in which every prefix or postfix of an input string is also accepted, if the prefix or postfix is in the language. It is shown that there are languages L Σ⁺ such that L is not recognizable by OCA in real-time and the reversal of L and the concatenation LΣ^* are recognizable by CA in real-time.},
keywords={},
doi={10.1093/ietisy/e88-d.1.65},
ISSN={},
month={January},}

Copy

TY - JOUR
TI - Real-Time Recognition of Cyclic Strings by One-Way and Two-Way Cellular Automata
T2 - IEICE TRANSACTIONS on Information
SP - 65
EP - 71
AU - Katsuhiko NAKAMURA
PY - 2005
DO - 10.1093/ietisy/e88-d.1.65
JO - IEICE TRANSACTIONS on Information
SN -
VL - E88-D
IS - 1
JA - IEICE TRANSACTIONS on Information
Y1 - January 2005
AB - This paper discusses real-time language recognition by 1-dimensional one-way cellular automata (OCAs) and two-way cellular automata (CAs), focusing on limitations of the parallel computation power. To clarify the limitations, we investigate real-time recognition of cyclic strings of the form u^k with u {0,1}⁺ and k 2. We show a version of pumping lemma for recognizing cyclic strings by OCAs, which can be used for proving that several languages are not recognizable by OCAs in real time. The paper also discusses the real-time language recognition of CAs by prefix and postfix computation, in which every prefix or postfix of an input string is also accepted, if the prefix or postfix is in the language. It is shown that there are languages L Σ⁺ such that L is not recognizable by OCA in real-time and the reversal of L and the concatenation LΣ^* are recognizable by CA in real-time.
ER -