Characterizing derivation trees of context-free grammars through a generalization of finite automata theory
From MaRDI portal
Publication:2526960
DOI10.1016/S0022-0000(67)80022-9zbMath0155.01802MaRDI QIDQ2526960
Publication date: 1967
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Related Items
Nested Regular Expressions Can Be Compiled to Small Deterministic Nested Word Automata, Cooperating Distributed Tree Automata, Defining syntax-directed translations by tree bimorphisms, Learning deterministic context free grammars: the Omphalos competition, Mappings and grammars on trees, XML schema, tree logic and sheaves automata, Weighted tree automata with constraints, Gaifman's theorem on categorial grammars revisited, On Commutative and Nonassociative Syntactic Calculi and Categorial Grammars, On the minimization of XML schemas and tree automata for unranked trees, Algebraic structures in categorial grammar, Operator Precedence Languages: Their Automata-Theoretic and Logic Characterization, Simplifying XML schema: single-type approximations of regular tree languages, Weighted Unranked Tree Automata over Tree Valuation Monoids and Their Characterization by Weighted Logics, Tree transducers, L systems, and two-way machines, Forward and backward application of symbolic tree transducers, Ambiguity Hierarchies for Weighted Tree Automata, Aperiodicity, Star-freeness, and First-order Logic Definability of Operator Precedence Languages, Unnamed Item, Learning Tree Languages, Weighted logics for unranked tree automata, Sulla complessita di alcuni problemi di conteggio, Weighted bottom-up and top-down tree transformations are incomparable, Some results in tree automata, Solving the Weighted HOM-Problem With the Help of Unambiguity, Boundary graph grammars with dynamic edge relabeling, On the time and tape complexity of weak unification, Generalizing input-driven languages: theoretical and practical benefits, Tree Automata for Non-linear Arithmetic, Tree acceptors and grammar forms, Semantic preserving translations, Unnamed Item, Recognizable formal power series on trees, On the structure of context-sensitive grammars, Operator precedence temporal logic and model checking, Unnamed Item, Pebble machines and tree walking machines, Unnamed Item, The string generating power of context-free hypergraph grammars, Multidimensional trees, Property testing of regular tree languages, Structural equivalence and ET0L grammars, Weighted monadic Datalog, Logic and linguistics meeting, Stanford, 1987, Automata for unordered trees, Extending two-variable logic on data trees with order on data values and its automata, THE REGULARITY OF TWO-WAY NONDETERMINISTIC TREE AUTOMATA LANGUAGES, Monadic Second-Order Logic and Transitive Closure Logics over Trees, Operator precedence and the visibly pushdown property, An extrinsic characterization of addressable data graphs, Natural state transformations, Cascades of tree-automata and computations in universal algebras, The derivation language of a phrase structure grammar, Tree adjunct grammars, A multidimensional approach to syntactic pattern recognition, Weighted tree automata with constraints, Surface tree languages and parallel derivation trees, Augmented transition networks and their relation to tree transducers, Bottom-up unranked tree-to-graph transducers for translation into semantic graphs, Inference for regular bilanguages, AN ALGEBRAIC APPROACH TO MSO-DEFINABILITY ON COUNTABLE LINEAR ORDERINGS, Unnamed Item, Inessential features, ineliminable features, and modal logics for model theoretic syntax, An algebraic technique for context-sensitive parsing, Recognizability in the Simply Typed Lambda-Calculus, Generalized sequential machine maps, Probabilistic tree automata and context free languages, Weighted operator precedence languages, DECISION PROBLEMS ON PATH-CONTROLLED GRAMMARS, Efficient inclusion checking for deterministic tree automata and XML schemas, Weighted Operator Precedence Languages, Theory of formal grammars, Three hierarchies of transducers, Implementation of data types by algebraic methods, Tree pushdown automata, Covering-languages of grammars, A note on the strong and weak generative powers of formal systems, wMSO theories as grammar formalisms, Ambiguity hierarchies for weighted tree automata
Cites Work
