Linear indexed languages
From MaRDI portal
Publication:797293
DOI10.1016/0304-3975(84)90023-9zbMath0545.68067OpenAlexW2003872603MaRDI QIDQ797293
Publication date: 1984
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(84)90023-9
homomorphic imagescontext-free langugesfull principal semi-AFLlinear indexed languagesParikh theorem
Related Items
Grammars, derivation modes and properties of indexed and type-0 languages ⋮ Self-embedding indexed grammars ⋮ Indexed counter languages ⋮ Deterministic pushdown-CD-systems of stateless deterministic R(1)-automata ⋮ The OI-hierarchy is closed under control ⋮ The structure of index sets and reduced indexed grammars ⋮ Calibrating generative models: the probabilistic Chomsky-Schützenberger hierarchy ⋮ The equivalence of four extensions of context-free grammars ⋮ Two applications of monoid actions to cross-sections ⋮ Iterated linear control and iterated one-turn pushdowns ⋮ A pumping lemma for flip-pushdown languages ⋮ A language hierarchy of binary relations ⋮ A geometric hierarchy beyond context-free languages ⋮ Relationships between bounded languages, counter machines, finite-index grammars, ambiguity, and commutative regularity ⋮ Storage products and linear control of derivations ⋮ Basic tree transducers ⋮ Grammatical characterizations of NPDAs and VPDAs with counters ⋮ Epsilon-reducible context-free languages and characterizations of indexed languages ⋮ Gaining Power by Input Operations: Finite Automata and Beyond ⋮ On finite-index indexed grammars and their restrictions ⋮ On Bounded Semilinear Languages, Counter Machines, and Finite-Index ET0L ⋮ Semilinearity of Families of Languages
Cites Work
