✦ LIBER ✦

Ambiguity in omega context free languages

✍ Scribed by Olivier Finkel

Publisher: Elsevier Science
Year: 2003
Tongue: English
Weight: 522 KB
Volume: 301
Category: Article
ISSN: 0304-3975
DOI: 10.1016/s0304-3975(02)00584-4

No coin nor oath required. For personal study only.

✦ Synopsis

We extend the well-known notions of ambiguity and of degrees of ambiguity of ÿnitary context free languages to the case of omega context free languages (!-CFL) accepted by B uchi or Muller pushdown automata. We show that these notions may be deÿned independently of the B uchi or Muller acceptance condition which is considered. We investigate ÿrst properties of the subclasses of omega context free languages we get in that way, giving many examples and studying topological properties of !-CFL of a given degree of ambiguity.

📜 SIMILAR VOLUMES

Borel hierarchy and omega context free l

Borel hierarchy and omega context free languages

✍ Olivier Finkel 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 214 KB

We give in this paper additional answers to questions of Lescow and Thomas (A decade of

A note on the density of inherently ambi

A note on the density of inherently ambiguous context-free languages

✍ R. Kemp 📂 Article 📅 1980 🏛 Springer-Verlag 🌐 English ⚖ 139 KB

Bracketed context-free languages

✍ Seymour Ginsburg; Michael A. Harrison 📂 Article 📅 1967 🏛 Elsevier Science 🌐 English ⚖ 1012 KB

A bracketed grammar is a context-free grammar in which indexed brackets are inserted around the right-hand sides of the rules. The language generated by a bracketed grammar is a bracketed language. An algebraic condition is given for one bracketed language to be a subset of another. The intersection

On omega context free languages which ar

On omega context free languages which are Borel sets of infinite rank

✍ Olivier Finkel 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 296 KB

This paper is a continuation of the study of topological properties of omega context free languages (!-CFL). We proved in (Topological properties of omega context free languages, Theoretical Computer Science, 262 (1-2) (2001) 669-697) that the class of !-CFL exhausts the ÿnite ranks of the Borel hie

Transposition errors in context-free lan

Transposition errors in context-free languages

✍ K. Humenik; R.S. Pinkham 📂 Article 📅 1992 🏛 Elsevier Science 🌐 English ⚖ 789 KB

Length considerations in context-free la

Length considerations in context-free languages

✍ Danny Raz 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 905 KB

In this paper we investigate languages containing at most a bounded number of words of each length. We first show that the context-free languages for which the number of words of every length is bounded by a fixed polynomial are exactly the bounded context-free languages in the sense of . Thus, we p