๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Simulation of one-dimensional cellular automata by uniquely parallel parsable grammars

โœ Scribed by Jia Lee; Katsunobu Imai; Kenichi Morita

Publisher
Elsevier Science
Year
2003
Tongue
English
Weight
260 KB
Volume
304
Category
Article
ISSN
0304-3975

No coin nor oath required. For personal study only.

โœฆ Synopsis

A uniquely parsable grammar (UPG) introduced by Morita et al. (Acta Inform. 34 (1997) ) is a special kind of generative grammar where parsing can be performed without backtracking. By extending a UPG, a uniquely parallel parsable grammar (UPPG) was proposed and its unique parallel parsability has been investigated. In this paper, we show any one-dimensional cellular automaton, as a parallel language recognition device, can be simply simulated by a parallel reduction in an equivalent UPPG.

๐Ÿ“œ SIMILAR VOLUMES

Automaticity of double sequences generat
Automaticity of double sequences generated by one-dimensional linear cellular automata
โœ J.-P Allouche; F von Haeseler; H.-O Peitgen; A Petersen; G Skordev ๐Ÿ“‚ Article ๐Ÿ“… 1997 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 991 KB

We give a complete answer to the question whether a double sequence that is generated by a one-dimensional linear cellular automaton, and whose states are integers modulo m, is k-automatic or not.