Indexed Grammars—An Extension of Context-Free Grammars
From MaRDI portal
Publication:5565119
DOI10.1145/321479.321488zbMath0175.27801OpenAlexW2442545619WikidataQ56135109 ScholiaQ56135109MaRDI QIDQ5565119
Publication date: 1968
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/321479.321488
Related Items (only showing first 100 items - show all)
On two-way tree automata ⋮ The grammar of mammalian brain capacity ⋮ Boolean grammars ⋮ Pushdown machines for the macro tree transducer ⋮ Transducers and the decidability of independence in free monoids ⋮ Solution Sets for Equations over Free Groups are EDT0L Languages ⋮ An Approach to Computing Downward Closures ⋮ Grammars, derivation modes and properties of indexed and type-0 languages ⋮ Yield-languages of two-way pushdown tree automata ⋮ Self-embedding indexed grammars ⋮ Indexed counter languages ⋮ Recognition of perfect labeled trees with regularity condition ⋮ The OI-hierarchy is closed under control ⋮ On the word problem for special monoids ⋮ Deterministic tree pushdown automata and monadic tree rewriting systems ⋮ The structure of index sets and reduced indexed grammars ⋮ On the rational subset problem for groups. ⋮ Deletion operations on deterministic families of automata ⋮ Calibrating generative models: the probabilistic Chomsky-Schützenberger hierarchy ⋮ Recursion Schemes and the WMSO+U Logic ⋮ A Note on Decidable Separability by Piecewise Testable Languages ⋮ Weighted iterated linear control ⋮ Iterated linear control and iterated one-turn pushdowns ⋮ Fundamental methodological issues of syntactic pattern recognition ⋮ Stochastic grammars and languages ⋮ On some families of languages related to developmental systems ⋮ On the word problem for free products of semigroups and monoids ⋮ Restarting Tree Automata and Linear Context-Free Tree Languages ⋮ Simply typed fixpoint calculus and collapsible pushdown automata ⋮ A note on Lindenmayer systems, Szilard languages, spectra, and equivalence ⋮ The IO- and OI-hierarchies ⋮ The complexity of verbal languages over groups ⋮ A language hierarchy of binary relations ⋮ Queues, stacks, and transcendentality at the transition to chaos ⋮ Yield-languages recognized by alternating tree recognizers ⋮ Multidimensional trees ⋮ GROUPS WITH CONTEXT-FREE CONJUGACY PROBLEMS ⋮ Context-free grammars with lookahead ⋮ Iterated stack automata and complexity classes ⋮ A shrinking lemma for indexed languages ⋮ Literal homomorphisms of ol-languagest ⋮ Literal homomorphisms of ol-languagest ⋮ An infinite hierarchy induced by depth synchronization ⋮ Parallel OL-languages ⋮ A geometric hierarchy beyond context-free languages ⋮ THE REGULARITY OF TWO-WAY NONDETERMINISTIC TREE AUTOMATA LANGUAGES ⋮ Unnamed Item ⋮ On the complexity of finite, pushdown, and stack automata ⋮ Observations about bounded languages and developmental systems ⋮ Pushdown tree automata ⋮ On coupled languages and translations ⋮ On procedures as open subroutines. II ⋮ Global index grammars and descriptive power ⋮ On grammar forms with terminal context ⋮ The generative capacity of block-synchronized context-free grammars ⋮ On derivation trees of indexed grammars - an extension of the uvwxy- theorem ⋮ A note on K-iteration grammars ⋮ Tree adjunct grammars ⋮ On the synchronized derivation depth of context-free grammars ⋮ Two-way nested stack automata are equivalent to two-way stack automata ⋮ Un théorème de duplication pour les forets algébriques ⋮ Iterated pushdown automata and sequences of rational numbers ⋮ Linear-bounded composition of tree-walking tree transducers: linear size increase and complexity ⋮ A relationship between ETOL and EDTOL languages ⋮ Hypergrammars: An extension of macrogrammars ⋮ Basic tree transducers ⋮ Look-ahead on pushdowns ⋮ Degree-languages: A new concept of acceptance ⋮ Grammatical characterizations of NPDAs and VPDAs with counters ⋮ Augmented transition networks and their relation to tree transducers ⋮ A pattern representation of indexed languages ⋮ Epsilon-reducible context-free languages and characterizations of indexed languages ⋮ Weighted automata with storage ⋮ A new pumping lemma for indexed languages, with an application to infinite words ⋮ Effective constructions in well-partially-ordered free monoids ⋮ A Survey on Decidable Equivalence Problems for Tree Transducers ⋮ Pumping lemmas for term languages ⋮ Two complementary operations inspired by the DNA hairpin formation: Completion and reduction ⋮ On finite-index indexed grammars and their restrictions ⋮ General decidability results for asynchronous shared-memory programs: higher-order and beyond ⋮ Monoid-Based Approach to the Inclusion Problem on Superdeterministic Pushdown Automata ⋮ Checking automata and one-way stack languages ⋮ The calculi of emergence: Computation, dynamics and induction ⋮ Generalized sequential machine maps ⋮ Principal abstract families of weighted tree languages ⋮ Deterministic acceptors for indexed languages ⋮ Direction controlled programmed grammars ⋮ Time and space complexity of inside-out macro languages ⋮ GROUPS WITH INDEXED CO-WORD PROBLEM ⋮ Theory of formal grammars ⋮ IDL-PMCFG, a grammar formalism for describing free word order languages ⋮ Linear indexed languages ⋮ Hierarchies of hyper-AFLs ⋮ Pushdown tree automata, algebraic tree systems, and algebraic tree series ⋮ Model-Checking Games for Typed λ-Calculi ⋮ Extended macro grammars and stack controlled machines ⋮ The IO and OI hierarchies revisited ⋮ Decidability of structural equivalence of E0L grammars ⋮ On two families of forests ⋮ Counting with range concatenation grammars
This page was built for publication: Indexed Grammars—An Extension of Context-Free Grammars
