One counter languages and the IRS condition

DOI10.1016/S0022-0000(75)80042-0zbMath0307.68062MaRDI QIDQ1218284

Sheila A. Greibach

Publication date: 1975

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

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (17)

Context-free grammars with cancellation properties ⋮ Sur la structure des langages algébriques ⋮ Unnamed Item ⋮ On the usefulness of bifaithful rational cones ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Langages algébriques déterministes non générateurs ⋮ A new class of C.F.L. for which the equivalence is decidable ⋮ Simple deterministic NTS languages ⋮ On nonstochastic languages and homomorphic images of stochastic languages ⋮ On some transducer equivalence problems for families of languages ⋮ Trees and languages with periodic signature ⋮ Unnamed Item ⋮ Générateurs algébriques et systèmes de paires iterantes ⋮ On some bounded semiAFLs and AFLs ⋮ Langages à un compteur ⋮ Remarques sur les langages de parenthèses

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Transductions des langages de Chomsky
• The inclusion of the substitution closure of linear and one-counter languages in the largest sub-AFL of the family of algebraic languages is proper
• Derivation-bounded languages
• Linear Automaton Transformations
• Erasable context-free languages
• On Relations Defined by Generalized Finite Automata
• Finite-Turn Pushdown Automata
• An Infinite Hierarchy of Context-Free Languages
• An analog of a theorem about context-free languages
• Chains of full AFL's
• Inclusion relations among families of context-free languages
• Erasing in context-free AFLs
• Phrase structure languages, finite machines, and channel capacity

This page was built for publication: One counter languages and the IRS condition