A note on the equivalence and complexity of linear grammars

Grammars Vol. 6, Iss.2, pp 115-126. 2003


José M. Sempere
Departamento de Sistemas Informáticos y Computación.
Universidad Politécnica de Valencia.
Camino de Vera s/n, 46022 Valencia (Spain).


Abstract

Linear languages can be characterized by regular-like expressions (linear expressions) according to a previous work [6]. In this paper, we consider some equivalence properties of linear expressions in order to obtain a characterization of reversal and Kolmogorov complexity of linear languages. First, we introduce the relationship between regular expressions equivalence properties and linear expressions equivalence properties. Then, we define permutation and compression equivalence properties in order to handle linear expressions to obtain shorter equivalent ones. The study of reversal and Kolmogorov complexities associated to linear grammars is performed in the rest of the paper. We obtain a speed-up theorem for reversal complexity. Finally, we define a Komogorov-like complexity associated to linear grammars and we deduce upper bounds for such complexity measure.

Keywords: Formal languages, linear grammars, equivalence properties, reversal complexity, Kolmogorov complexity.

Bibliography

[1] J. Chen, C. Yap. Reversal Complexity. SIAM Journal on Computing 20 4, pp 622-638. 1991.

[2] J. Gruska. A Characterization of Context-free languages. Journal of Computer and System Sciences 5, 353-364. 1971.

[3] K. Hashiguchi, H. Yoo. Extended regular expressions of star degree at most two. Theoretical Computer Science 76, 272-284. 1990.

[4] K. Hashiguchi. The Infinite 2-Star Height Hierarchy of Extended Regular Languages of Star Degree at Most Two. Information and Computation 114, 237-246. 1994.

[5] M. Li, P. Vitànyi. An Introduction to Kolmogorov Complexity and Its Applications. Springer-Verlag. 1993.

[6] J.M. Sempere. On a class of regular-like expressions for linear languages. Journal of Automata, Languages and Combinatorics 5 3, pp 343-354. 2000.

[7] A. Salomaa. Formal Languages. Academic Press, Inc. 1973.

[8] K. Wagner, G. Wechsung. Computational Complexity. D. Reidel Publishing Company. 1986.

[9] M.K. Yntema. Cap Expressions for Context-Free Languages. Information and Control 18, 311-318. 1971.

[10] H. Yoo, K. Hashiguchi. Extended automata-like regular expressions of star degree at most (2,1). Theoretical Computer Science 88, 351-363. 1991.