Abstract: Linear cellular automata with left-to-right communication are used for generating words. The terminal state of each cell corresponds to the symbol generated in the given position. In nondeterministic case such an automaton describes a language. The class obtained is exactly the class of context-sensitive languages. This fact provides a possible approach to defining context-sensitivity in the 2-dimensional case. In the deterministic case generating infinite words rather than finite ones seems to be of interest. We show that all fixed points of (productive) substitutions and — in the 2-dimensional case — both regular and modular trellises can be generated.
Publication Year: 1991
Publication Date: 1991-01-01
Language: en
Type: book-chapter
Indexed In: ['crossref']
Access and Citation
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot