Infinite trees in normal form and recursive equations having a unique solution

DOI10.1007/BF01744293zbMath0418.68013MaRDI QIDQ3851585

Bruno Courcelle

Publication date: 1979

Published in: Mathematical Systems Theory (Search for Journal in Brave)

zbMATH Keywords

program transformationscorrectness criteriatree rewriting systemequational classes of interpretationsequivalence of recursive program schemes

Mathematics Subject Classification ID

Specification and verification (program logics, model checking, etc.) (68Q60)

Related Items

An axiomatic approach to the Korenjak-Hopcroft algorithms, Algebraic semantics and complexity of term rewriting systems, Fully abstract submodels of typed lambda calculi, Equivalences and transformations of regular systems - applications to recursive program schemes and grammars, Static correctness of hierarchical procedures, Continuous monoids and yields of infinite trees, Computing in unpredictable environments: semantics, reduction strategies, and program transformations, Recursion-closed algebraic theories, Graph grammars and operational semantics, Rewrite, rewrite, rewrite, rewrite, rewrite, \dots, Algebraic and fixed point equations over inverse limits of algebras, Proving the correctness of recursion-based automatic program transformations, Conditional rewriting logic as a unified model of concurrency, Unnamed Item, Interpretations of recursively defined types, Proving the correctness of recursion-based automatic program transformations, Recursion induction principle revisited, An extension to trees of the Sardinas and Patterson algorithm, Fundamental properties of infinite trees, Deterministic and nondeterministic flowchart interpretations, Axiomatisation des tests, Computing in unpredictable environments: Semantics, reduction strategies, and program transformations

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A uniform approach to inductive posets and inductive closure
• A representation of trees by languages. II
• Knowledge and reasoning in program synthesis
• Program equivalence and context-free grammars
• A system which automatically improves programs
• Varieties of ordered algebras
• Completeness results for the equivalence of recursive schemas
• The inclusion problem for simple languages
• Equivalence problems for deterministic context-free languages and monadic recursion schemes
• On the algebraic structure of rooted trees
• Proving and applying program transformations expressed with second-order patterns
• On some classes of interpretations
• Flowgraphs and Flow Algebras
• Bases for Chain-complete Posets
• A Transformation System for Developing Recursive Programs
• Initial Algebra Semantics and Continuous Algebras
• Operational and semantic equivalence between recursive programs.
• Fixpoint approach to the theory of computation
• Tree-Manipulating Systems and Church-Rosser Theorems