Two iteration theorems for some families of languages

DOI10.1016/S0022-0000(73)80036-4zbMath0298.68053OpenAlexW2058929902MaRDI QIDQ1214758

Luc Boasson

Publication date: 1973

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0022-0000(73)80036-4

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items

A pumping lemma for real-time deterministic context-free languages ⋮ Unnamed Item ⋮ The interchange or pump (di)lemmas for context-free languages ⋮ On the usefulness of bifaithful rational cones ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Iteration theorems for families of strict deterministic languages ⋮ The different shades of infinite session types ⋮ Formal grammars for turn-bounded deterministic context-free languages ⋮ Two iteration theorems for the LL(k) languages ⋮ A new algorithm for regularizing one-letter context-free grammars. ⋮ Non-prinicipalité du cylindre des langages à compteur ⋮ Un théorème de Chomsky-Schützenberger pour les forets algébriques ⋮ Produit dans le cône rationnel engendre par D ⋮ Langages algébriques, paires iterantes et transductions rationnelles ⋮ Remarks on blind and partially blind one-way multicounter machines ⋮ A PUMPING CONDITION FOR ULTRALINEAR LANGUAGES ⋮ Sur une propriété d'itération des langages algébriques déterministes ⋮ Langages à un compteur

Uses Software

• ALGOL 60

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Transductions des langages de Chomsky
• Semigroups, Presburger formulas, and languages
• Principal AFL
• Rational sets in commutative monoids
• Sur diverses familles de langages fermées par transduction rationnelle
• On Relations Defined by Generalized Finite Automata
• A helpful result for proving inherent ambiguity
• An Infinite Hierarchy of Context-Free Languages
• Studies in abstract families of languages