Abstract
Lautemann et al. (1995) gave a descriptive characterisation of the class of context-free languages, showing that a language is context-free iff it is definable as the set of words satisfying some sentence of a particular logic (fragment) over words. The present notes discuss how to specialise this result to the class of linear languages. Somewhat surprisingly, what would seem the most straightforward specialisation actually fails, due to the fact that linear grammars fail to admit a Greibach normal form. We identify an alternative specialisation, based on an alternative characterisation of context-free languages, also noted by Lautemann et al. (1995).
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Amar, V., & Putzolu, G. (1964). On a family of linear grammars. Information and Control, 7, 283–291.
Eiter, T., Gottlob, G., & Gurevich, Y. (2000). Existential second-order logic over strings. Journal of the ACM, 47, 77–131.
Gécseg, F., & Steinby, M. (1997). Tree languages. In Rozenberg, G. and A. Salomaa, editors, Handbook of Formal Languages, vol. 3, Springer-Verlag.
Greibach, S. (1965). A new normal-form theorem for context-free phrase structure grammars. Journal of the ACM, 12, 42–52.
Hopcroft, J.E., & Ullman, J.D. (1979). Introduction to Automata Theory, Languages, and Computation. Addison–Wesley.
Langholm, T., & Bezem, M. (2003). A descriptive characterisation of even linear languages. Grammars 6, 169–181.
Lautemann, C., Schwentick, T., & Thérien, D. (1995). Logics for context-free languages. In Pacholsky, L. and J. Tiuryn, editors, Computer Science Logic, LNCS 933, 205–216. Springer-Verlag.
Rosenkrantz, D.J. (1967). Matrix equations and normal forms for context-free grammars. Journal of the ACM, 14, 501–507.
Thomas, W. (1997). Languages, Automata and Logic. In Rozenberg, G. and A. Salomaa, editors, Handbook of Formal Languages, Vol. 3, Springer-Verlag.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Langholm, T. A descriptive characterisation of linear languages. JoLLI 15, 233–250 (2006). https://doi.org/10.1007/s10849-006-9016-z
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10849-006-9016-z