Topology and ambiguity in \(\omega\)-context free languages
type: Item
instance of: scholarly article
title: Topology and ambiguity in \(\omega\)-context free languages
zbMATH Open document ID: 1080.68054
author: Olivier Finkel
author: P. Simonnet
published in: Bulletin of the Belgian Mathematical Society - Simon Stevin
publication date: 2005-06-09T00:00:00Z
full work available at URL: https://projecteuclid.org/euclid.bbms/1074791327
review text: In this paper the connection between the topological complexity of an \(\omega\)-context-free language (\(\omega\)-CF laguage) and its degree of ambiguity is shown. The \(\omega\)-CF languages are accepted by Büchi Pushdown Automata (BPDA), and the degree of ambiguity of a given infinite word is the number of different accepting runs in the automaton for this word. Using descriptive set theory it is proved that if \(L(A)\) is a non-Borel \(\omega\)-CF language accepted by BPDA \(A\), then there exist \(2^{\aleph_0}\) infinite words such that they have \(2^{\aleph_0}\) accepting runs in \(A\), where \(2^{\aleph_0}\) is the cardinality of the continuum. It follows that neither non-ambiguity nor inherent ambiguity are preserved by taking the adherence or the \(\delta\)-limit of a finitary CF language. The adherence of the set \(W\) of finite words is the set of all infinite words such that the set prefixes of an infinite word is a subset of the set of prefixes of \(W\), and the \(\delta\)-limit of \(W\) is a set of infinite words having infinitely many prefixes in \(W\). Also topology and ambiguity of infinitary rational relations is studied.
reviewed by: Vesa Halava
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 03D05
Mathematics Subject Classification ID: 03D55
Mathematics Subject Classification ID: 03E15
zbMATH DE Number: 2174590
zbMATH Keywords: context free languages
zbMATH Keywords: infinite words
zbMATH Keywords: infinitary rational relations
zbMATH Keywords: ambiguity
zbMATH Keywords: topological properties
zbMATH Keywords: Borel hierarchy
zbMATH Keywords: analytic sets
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 2174590