Finite generation of ambiguity in context-free languages
type: Item
instance of: scholarly article
title: Finite generation of ambiguity in context-free languages
zbMATH Open document ID: 0666.20030
DOI: 10.1016/0022-4049(89)90033-9
published in: Journal of Pure and Applied Algebra
publication date: 1989-01-01T00:00:00Z
review text: Let us recall that, for any pair \((L_ 1,L_ 2)\) of sub-languages of a context-free language L, the intersection \(L_ 1\cap L_ 2\) is said to be finitely presented if and only if there exist finitely many intersection components \(Z_ k\), algebraically generated sub-languages both of \(L_ 1\) and \(L_ 2\), partitioning \(L_ 1\cap L_ 2.\) First of all, this paper gives a categorical presentation for context- free languages generation: it permits particularly to model the ambiguity of a context-free language as a congruence on the category of derivations. Within this categorical model, a pair of sufficient conditions is presented so that, when a context-free grammar G is given, the intersection of a certain class of sub-languages of L(G) is finitely presented. When these conditions hold for a context-free grammar, the ambiguity of L(G) is shown to be finitely generated. The author establishes also that the conditions he gives cannot be necessary, because they are proved to be equivalent to undecidable problems for context-free grammars.
Mathematics Subject Classification ID: 20M35
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 18B99
zbMATH DE Number: 4089809
zbMATH Keywords: context-free language
zbMATH Keywords: intersection
zbMATH Keywords: finitely presented
zbMATH Keywords: intersection components
zbMATH Keywords: categorical presentation
zbMATH Keywords: context-free languages generation
zbMATH Keywords: ambiguity
zbMATH Keywords: congruence
zbMATH Keywords: category of derivations
zbMATH Keywords: context-free grammar
zbMATH Keywords: undecidable problems
author: Dana May Latch
reviewed by: Daniel Krob
MaRDI profile type: Publication
full work available at URL: 0022-4049(89)90033-9
OpenAlex ID: W2071745639
cites work: Can programming be liberated from the von Neumann style?
cites work: Q3677142
cites work: The basic algebraic structures in categories of derivations
cites work: Q5515373
cites work: Q3338216
cites work: Q5576254
cites work: Q3925859
cites work: Q5592246
cites work: A unification algorithm for typed \(\bar\lambda\)-calculus
cites work: Confluent Reductions: Abstract Properties and Applications to Term Rewriting Systems
cites work: Q3680248
cites work: Q5581665
cites work: FUNCTORIAL SEMANTICS OF ALGEBRAIC THEORIES
cites work: Q3915990
cites work: Q5639839
cites work: An Efficient Unification Algorithm
cites work: Categorical and topological aspects of formal languages
cites work: Linear unification
cites work: Q5678447
cites work: An algebraic model for programming languages
cites work: Q3338215
description: scientific article; zbMATH DE number 4089809