Linear indexed languages

DOI10.1016/0304-3975(84)90023-9MaRDI QIDQ797293zbMATH OpenOpenAlexFDO

Authors J. Duske, Rainer Parchmann

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

zbMATH Keywords

homomorphic imagescontext-free langugesfull principal semi-AFLlinear indexed languagesParikh theorem

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• Indexed counter languages
• scientific article; zbMATH DE number 3963215
• scientific article; zbMATH DE number 1972806

Cites work

• scientific article; zbMATH DE number 3963215 (Why is no real title available?)
• scientific article; zbMATH DE number 3660804 (Why is no real title available?)
• scientific article; zbMATH DE number 3509706 (Why is no real title available?)
• scientific article; zbMATH DE number 3639163 (Why is no real title available?)
• scientific article; zbMATH DE number 3311755 (Why is no real title available?)
• scientific article; zbMATH DE number 3413820 (Why is no real title available?)
• A geometric hierarchy of languages
• Control sets on grammars
• Indexed Grammars—An Extension of Context-Free Grammars

Cited in

(25)

• Relationships between bounded languages, counter machines, finite-index grammars, ambiguity, and commutative regularity
• On characterisation of language families in terms of inverse morphisms
• Epsilon-reducible context-free languages and characterizations of indexed languages
• Basic tree transducers
• Indexed counter languages
• Calibrating generative models: the probabilistic Chomsky-Schützenberger hierarchy
• scientific article; zbMATH DE number 3878381 (Why is no real title available?)
• A geometric hierarchy beyond context-free languages
• The structure of index sets and reduced indexed grammars
• Two applications of monoid actions to cross-sections
• scientific article; zbMATH DE number 3963215 (Why is no real title available?)
• A descriptive characterisation of linear languages
• Deterministic pushdown-CD-systems of stateless deterministic R(1)-automata
• On bounded semilinear languages, counter machines, and finite-index ET0L
• The equivalence of four extensions of context-free grammars
• A pumping lemma for flip-pushdown languages
• Grammars, derivation modes and properties of indexed and type-0 languages
• Self-embedding indexed grammars
• Gaining Power by Input Operations: Finite Automata and Beyond
• Storage products and linear control of derivations
• The OI-hierarchy is closed under control
• A language hierarchy of binary relations
• Grammatical characterizations of NPDAs and VPDAs with counters
• Semilinearity of families of languages
• Iterated linear control and iterated one-turn pushdowns

This page was built for publication: Linear indexed languages

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q797293)