Equivalences and transformations of regular systems - applications to recursive program schemes and grammars

DOI10.1016/0304-3975(86)90050-2zbMath0636.68104OpenAlexW2066030913MaRDI QIDQ1098322

Bruno Courcelle

Publication date: 1986

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(86)90050-2

zbMATH Keywords

context-free grammarsrewritingunfoldingrecursive definitionsRecursive program schemesrecursive systemsregular systems of equations

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Specification and verification (program logics, model checking, etc.) (68Q60)

Related Items

Correctness of fixpoint transformations, The greatest fixed-points and rational omega-tree languages, Handle-rewriting hypergraph grammars, Rules + strategies for transforming lazy functional logic programs, Parameter-reduction of higher level grammars, On flowchart theories. II: The nondeterministic case, Generation of polynomial-time algorithms for some optimization problems on tree-decomposable graphs, 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, Decomposable theories, Recognizable sets of graphs: equivalent definitions and closure properties, The monadic second-order logic of graphs, II: Infinite graphs of bounded width, Contributions to the semantics of logic perpetual processes, Continuous monoids and semirings, On inductive inference of cyclic structures, Computing in unpredictable environments: semantics, reduction strategies, and program transformations, Fixed point characterization of infinite behavior of finite-state systems, Object grammars and bijections., On systems of equations defining infinite graphs, The monadic second-order logic of graphs : Definable sets of finite graphs, Graph expressions and graph rewritings, Weighted graphs: A tool for studying the halting problem and time complexity in term rewriting systems and logic programming, The monadic second-order logic of graphs. V: On closing the gap between definability and recognizability, Contraction algebras and unification of (infinite) terms, Basic notions of universal algebra for language theory and graph grammars, The monadic second-order logic of graphs. IX: Machines and their behaviours, The monadic second-order logic of graphs. VII: Graphs as relational structures, Context-free hypergraph grammars have the same term-generating power as attribute grammars, A Büchi-like theorem for weighted tree automata over multioperator monoids, Equational tree transformations, Linearization in parallel pCRL, A Kleene theorem for weighted tree automata over distributive multioperator monoids, Computations by fly-automata beyond monadic second-order logic, Unnamed Item, DECOMPOSITION OF WEIGHTED MULTIOPERATOR TREE AUTOMATA, Recursive queries and context-free graph grammars, Equational Weighted Tree Transformations with Discounting, Equational weighted tree transformations, Attributed tree grammars, Weighted systems of equations, The monadic second-order logic of graphs. IV: Definability properties of equational graphs, The evaluation of first-order substitution is monadic second-order compatible, Equivalence of recursive specifications in process algebra, Computing in unpredictable environments: Semantics, reduction strategies, and program transformations

Uses Software

• ALGOL 60

Cites Work

• The solutions of two star-height problems for regular trees
• Iterative algebras
• All solutions of a system of recursion equations in infinite trees and other contraction theories
• A uniform approach to inductive posets and inductive closure
• Speeding up circularity tests for attribute grammars
• Fundamental properties of infinite trees
• Algebraic solutions to recursion schemes
• Metric interpretations of infinite trees and semantics of non deterministic recursive programs
• A representation of trees by languages. II
• The undecidability of a word problem: On a conjecture of Strong, Maggiolo-Schettini and Rosen
• An algebraic definition for control structures
• Nondeterministic flowchart programs with recursive procedures: Semantics and correctness. II
• Recursion-closed algebraic theories
• The IO- and OI-hierarchies
• Attribute grammars and recursive program schemes. I. II
• Fixed point theorems and semantics: A folk tale
• Completeness results for the equivalence of recursive schemas
• Least fixed points revisited
• A compactification of the algebra of terms
• Étude syntaxique de certains langages solutions d'équations avec opérateurs
• IO and OI. II
• On some classes of interpretations
• Program transformations and algebraic semantics
• About the rewriting systems produced by the Knuth-Bendix completion algorithm
• Proofs of partial correctness for attribute grammars with applications to recursive procedures and logic programming
• n-Rational Algebras II. Varieties and Logic of inequalities
• The validity of equations of complex algebras
• Varieties of ”If-Then-Else“
• Infinite trees in normal form and recursive equations having a unique solution
• Compatible Orderings on the Metric Theory of Trees
• Solutions of the Iteration Equation and Extensions of the Scalar Iteration Operation
• Confluent Reductions: Abstract Properties and Applications to Term Rewriting Systems
• On varieties closed under the construction of power algebras
• Bases for Chain-complete Posets
• Bottom-up and top-down tree transformations— a comparison
• The denotational semantics of programming languages
• A Transformation System for Developing Recursive Programs
• Initial Algebra Semantics and Continuous Algebras
• Can programming be liberated from the von Neumann style?
• Minimal and Optimal Computations of Recursive Programs
• An order-algebraic definition of knuthian semantics
• On Relations Defined by Generalized Finite Automata
• Algebraic automata and context-free sets
• Parenthesis Grammars
• Tree generating regular systems
• Automata in general algebras
• The minimalization of tree automata
• Two Families of Languages Related to ALGOL
• Fixpoint approach to the theory of computation
• On context-free languages and push-down automata
• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item