Abstract
Triangular trellis automata, also studied under the name of one-way real-time cellular automata, have been known for several decades as a purely abstract model of parallel computers. This paper establishes their computational equivalence to linear conjunctive grammars, which are linear context-free grammars extended with an explicit intersection operation. This equivalence allows to combine the known results on the generative power and closure properties of triangular trellis automata and linear conjunctive grammars and to obtain new previously unexpected results on this language family — for instance, to determine their exact relationship with other comparable families of languages.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
References
C. Choffrut and K. Culik II, “On real-time cellular automata and trellis automata”, Acta Informatica, 21 (1984), 393–407.
K. Culik II, J. Gruska and A. Salomaa, “Systolic trellis automata” (I, II), International Journal of Computer Mathematics, 15 (1984) 195–212; 16 (1984) 3-22.
C. Dyer, ”One-way bounded cellular automata”, Information and Control, 44 (1980), 261–281.
A. Okhotin, “Conjunctive grammars”, Journal of Automata, Languages and Combinatorics, 6:4 (2001), 519–535.
A. Okhotin, “A recognition and parsing algorithm for arbitrary conjunctive grammars”, Theoretical Computer Science, to appear.
A. Okhotin, “On the closure properties of linear conjunctive languages”, Theoretical Computer Science, to appear.
I. H. Sudborough, “A note on tape-bounded complexity classes and linear contextfree languages”, Journal of the ACM, 22:4 (1975), 499–500.
V. Terrier, “On real-time one-way cellular array”, Theoretical Computer Science, 141 (1995), 331–335.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Okhotin, A. (2003). Automaton Representation of Linear Conjunctive Languages. In: Ito, M., Toyama, M. (eds) Developments in Language Theory. DLT 2002. Lecture Notes in Computer Science, vol 2450. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45005-X_35
Download citation
DOI: https://doi.org/10.1007/3-540-45005-X_35
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-40431-6
Online ISBN: 978-3-540-45005-4
eBook Packages: Springer Book Archive