IO and OI. I

DOI10.1016/S0022-0000(77)80034-2zbMath0366.68053OpenAlexW4212777788MaRDI QIDQ1241985

Erik Meineche Schmidt, Joost Engelfriet

Publication date: 1977

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0022-0000(77)80034-2

Mathematics Subject Classification ID

Formal languages and automata (68Q45) General topics in the theory of software (68N01)

Related Items (46)

Closure properties of linear context-free tree languages with an application to optimality theory ⋮ Transducers and the decidability of independence in free monoids ⋮ Axiomatizing the equational theory of regular tree languages ⋮ High level tree transducers and iterated pushdown tree transducers ⋮ Compositions of tree series transformations ⋮ Branching synchronization grammars with nested tables ⋮ Unnamed Item ⋮ Generated models and the ω-rule: The nondeterministic case ⋮ The generative power of delegation networks ⋮ Towards more precise rewriting approximations ⋮ Decidable subcases of the equivalence problem for recursive program schemes ⋮ Iterated linear control and iterated one-turn pushdowns ⋮ Graph expressions and graph rewritings ⋮ Languages with homomorphic replacements ⋮ The equivalence of tree adjoining grammars and monadic linear context-free tree grammars ⋮ The formal power of one-visit attribute grammars ⋮ From Tree-Based Generators to Delegation Networks ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Alphabetic tree relations ⋮ Multiple context-free tree grammars: lexicalization and characterization ⋮ Extending regular expressions with homomorphic replacement ⋮ Composition closure of linear extended top-down tree transducers ⋮ Second-order abstract categorial grammars as hyperedge replacement grammars ⋮ Equational tree transformations ⋮ Recognizability of graph and pattern languages ⋮ Hasse diagrams for classes of deterministic bottom-up tree-to-tree-series transformations ⋮ Weighted automata with storage ⋮ Extended linear macro grammars, iteration grammars, and register programs ⋮ Two Equivalent Regularizations for Tree Adjoining Grammars ⋮ Formal computations of non deterministic recursive program schemes ⋮ Decidability of the finiteness of ranges of tree transductions ⋮ Principal abstract families of weighted tree languages ⋮ Equational Weighted Tree Transformations with Discounting ⋮ Equational weighted tree transformations ⋮ On the Mild Context-Sensitivity of k-Tree Wrapping Grammar ⋮ Hierarchies of tree series transformations ⋮ Time and space complexity of inside-out macro languages ⋮ Unique, guarded fixed points in an additive setting ⋮ Tree-based picture generation ⋮ Pushdown tree automata, algebraic tree systems, and algebraic tree series ⋮ Attributed tree grammars ⋮ Decidability of EDT0L structural equivalence ⋮ Minimality in a Linear Calculus with Iteration ⋮ R-fuzzy computation ⋮ An operational and denotational approach to non-context-freeness

Uses Software

• ALGOL 60

Cites Work

• A generalized approach to formal languages
• Simple program schemes and formal languages
• Generalized sequential machine maps
• A note on infinite trees
• Decidable Properties of Monadic Functional Schemas
• Bottom-up and top-down tree transformations— a comparison
• Data Types as Lattices
• Initial Algebra Semantics and Continuous Algebras
• Inductive methods for proving properties of programs
• Algebraic automata and context-free sets
• Generalized finite automata theory with an application to a decision problem of second-order logic
• An extension of ALGOL-like languages
• Two Families of Languages Related to ALGOL
• Mappings and grammars on trees
• Heterogeneous algebras
• Equational languages
• Tree-Manipulating Systems and Church-Rosser Theorems
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: IO and OI. I