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 (79)
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
This page was built for publication: Characterizing derivation trees of context-free grammars through a generalization of finite automata theory
