Context-free text grammars
type: Item
instance of: scholarly article
title: Context-free text grammars
zbMATH Open document ID: 0790.68061
DOI: 10.1007/BF01192159
published in: Acta Informatica
publication date: 1994-06-02T00:00:00Z
review text: A text is a triple \(\tau=(\lambda,\rho_ 1,\rho_ 2)\) such that \(\lambda\) is a labeling function, and \(\rho_ 1\) and \(\rho_ 2\) are linear orders on the domain of \(\lambda\); hence \(\tau\) may be seen as a word \((\lambda,\rho_ 1)\) together with an additional linear order \(\rho_ 2\) on the domain of \(\lambda\). The order \(\rho_ 2\) is used to give to the word \((\lambda,\rho_ 1)\) its individual hierarchical representation (syntactic structure) which may be a tree but it may be also more general than a tree. In this paper we introduce context-free grammars for texts and investigate their basic properties. Since each text has its own individual structure, the role of such a grammar should be that of a definition of a pattern common to all individual texts. This leads to the notion of a shapley context-free text grammar also investigated in this paper.
Mathematics Subject Classification ID: 68Q42
zbMATH DE Number: 567336
zbMATH Keywords: context-free grammars
zbMATH Keywords: texts
author: Andrzej Ehrenfeucht
author: Paulien ten Pas
author: Grzegorz Rozenberg
MaRDI profile type: Publication
cites work: Theory of 2-structures. I: Clans, basic subclasses, and morphisms
cites work: Theory of 2-structures. II: Representation through labeled tree families
cites work: Angular 2-structures
cites work: T-structures, T-functions, and texts
cites work: Combinatorial properties of texts
cites work: Q5678435
full work available at URL: https://doi.org/10.1007/bf01192159
OpenAlex ID: W2031277438
description: scientific article; zbMATH DE number 567336