TEXT LANGUAGES IN AN ALGEBRAIC FRAMEWORK

Article type: Research Article

Authors: Hoogeboom, Hendrik Jan | Pas, Paulienten

Affiliations: Department of Computer Science, Leiden University, P.O.Box 9512, 2300 RA Leiden, The Netherlands. hjh@rulwinw.leidenuniv.nl, pas@rulwinw.leidenuniv.nl

Abstract: A text can be defined as a word w together with a (second) linear order on its domain {1,..., |w|}. This second order may be used to define a hierarchical, tree-like, structure representing the text. The family of context-free sets of texts is investigated, i.e., sets of texts defined by context-free text grammars. In particular, those sets of texts are studied in the framework of universal algebra. This allows to compare the classical notions of equational and recognizable families in an algebra with context-free sets in the “algebra of texts”. Within this algebra the notion of equational sets coincides with the context-free sets. A grammatical characterization of the family of recognizable sets is given as a subfamily of the context-free sets of texts.

DOI: 10.3233/FI-1996-253409

Journal: Fundamenta Informaticae, vol. 25, no. 3-4, pp. 353-380, 1996