Algebraic automata and context-free sets
From MaRDI portal
Publication:5536635
DOI10.1016/S0019-9958(67)90353-1zbMath0155.34301OpenAlexW2050407768MaRDI QIDQ5536635
Publication date: 1967
Published in: Information and Control (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0019-9958(67)90353-1
Related Items
A Model-Theoretic Description of Tree Adjoining Grammars1 1The research presented in this paper was supported by the Deutsche Forschungsgemeinschaft within the Sonderforschungsbereich 441, TP A2. The authors wish to thank Jens Michaelis and Stephan Kepser for helpful comments. ⋮ Handle-rewriting hypergraph grammars ⋮ Existential MSO over two successors is strictly weaker than over linear orders ⋮ Fuzzy tree automata ⋮ Definable transductions and weighted logics for texts ⋮ Equivalences and transformations of regular systems - applications to recursive program schemes and grammars ⋮ An Algebraic Characterization of Semirings for Which the Support of Every Recognizable Series Is Recognizable ⋮ An axiomatic definition of context-free rewriting and its application to NLC graph grammars ⋮ The monadic second-order logic of graphs. I: Recognizable sets of finite graphs ⋮ Monadic second-order definable text languages ⋮ Recognizable sets of graphs: equivalent definitions and closure properties ⋮ Mappings and grammars on trees ⋮ Unnamed Item ⋮ Context-sensitive string languages and recognizable picture languages ⋮ Finite loops recognize exactly the regular open languages ⋮ A geometrical view of the determinization and minimization of finite-state automata ⋮ Logical description of context-free graph languages ⋮ Tree algebras and varieties of tree languages ⋮ MSO definable text languages ⋮ The generative power of delegation networks ⋮ Efficient enumeration of weighted tree languages over the tropical semiring ⋮ Object grammars and bijections. ⋮ A structural/temporal query language for business processes ⋮ The monadic second-order logic of graphs : Definable sets of finite graphs ⋮ Graph expressions and graph rewritings ⋮ Logics and Automata for Totally Ordered Trees ⋮ Recursion-closed algebraic theories ⋮ The IO- and OI-hierarchies ⋮ Equivalent definitions of recognizability for sets of graphs of bounded tree-width ⋮ An algebraic characterization of semirings for which the support of every recognizable series is recognizable ⋮ Pebble machines and tree walking machines ⋮ On rational definitions in complete algebras without rank ⋮ Conservative groupoids recognize only regular languages ⋮ The monadic second-order logic of graphs. V: On closing the gap between definability and recognizability ⋮ Basic notions of universal algebra for language theory and graph grammars ⋮ The monadic second-order logic of graphs. IX: Machines and their behaviours ⋮ Variable Tree Automata over Infinite Ranked Alphabets ⋮ Context-free hypergraph grammars have the same term-generating power as attribute grammars ⋮ On characterization of fuzzy tree pushdown automata ⋮ Algebraic recognizability of regular tree languages ⋮ Equational tree transformations ⋮ Natural state transformations ⋮ Recognizability of graph and pattern languages ⋮ Recognizability, hypergraph operations, and logical types ⋮ Adaptive star grammars and their languages ⋮ Bottom-up unranked tree-to-graph transducers for translation into semantic graphs ⋮ IO and OI. I ⋮ IO and OI. II ⋮ Extended linear macro grammars, iteration grammars, and register programs ⋮ Stone duality, topological algebra, and recognition. ⋮ Unnamed Item ⋮ The HOM Problem is EXPTIME-Complete ⋮ ALGEBRAIC LINEAR ORDERINGS ⋮ Recursive queries and context-free graph grammars ⋮ Recognizability in the Simply Typed Lambda-Calculus ⋮ Decidability of the finiteness of ranges of tree transductions ⋮ Generalized sequential machine maps ⋮ Nondeterministic operations on finite relational structures ⋮ Equational Weighted Tree Transformations with Discounting ⋮ Expressive power of typed and type-free programming languages ⋮ Series-parallel languages and the bounded-width property ⋮ BOOLEAN FUZZY SETS ⋮ Equational weighted tree transformations ⋮ Decidability and complexity of simultaneous rigid E-unification with one variable and related results ⋮ A Mezei-Wright theorem for categorical algebras ⋮ The recognizability of sets of graphs is a robust property ⋮ A comparison of tree transductions defined by monadic second order logic and by attribute grammars ⋮ Tree-based picture generation ⋮ Theory of formal grammars ⋮ Rationality in algebras with a series operation ⋮ The star problem and the finite power property in trace monoids: Reductions beyond C4 ⋮ Attributed tree grammars ⋮ Macro tree transducers ⋮ An operational and denotational approach to non-context-freeness
This page was built for publication: Algebraic automata and context-free sets
