Fundamental properties of infinite trees

DOI10.1016/0304-3975(83)90059-2zbMath0521.68013OpenAlexW4212983671WikidataQ55921412 ScholiaQ55921412MaRDI QIDQ1055184

Publication date: 1983

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

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

zbMATH Keywords

formal languages semantics of programming languages combinatorics of the free monoid

Mathematics Subject Classification ID

Semantics in the theory of computing (68Q55) Specification and verification (program logics, model checking, etc.) (68Q60) General topics in the theory of software (68N01)

Related Items

Explicit cyclic substitutions, Deconfined Global Types for Asynchronous Sessions, An axiomatic approach to the Korenjak-Hopcroft algorithms, Order-theoretic Trees: Monadic Second-order Descriptions and Regularity, Inference Systems with Corules for Combined Safety and Liveness Properties of Binary Session Types, Type reconstruction with recursive types and atomic subtyping, Extending Co-logic Programs for Branching-Time Model Checking, Algebraic semantics and complexity of term rewriting systems, Unnamed Item, Contracts for Mobile Processes, Prolog infinite trees and automata, Decomposable theories, Doctrines, modalities and comonads, The monadic second-order logic of graphs, II: Infinite graphs of bounded width, Continuous monoids and yields of infinite trees, Unnamed Item, Algèbres effectives dans la programmation logique avec contraintes, Rational rewriting, Checked corecursive streams: expressivity and completeness, Productive corecursion in logic programming, A relaxed condition for avoiding the occur-check, A logical framework with higher-order rational (circular) terms, Unfoldings and Coverings of Weighted Graphs, Decidable subcases of the equivalence problem for recursive program schemes, Partially Typed Multiparty Sessions, On systems of equations defining infinite graphs, On frontiers of regular trees, Graph expressions and graph rewritings, A simple library implementation of binary sessions, Finiteness and rational sequences, constructively, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Flexible coinductive logic programming, The New Normal: We Cannot Eliminate Cuts in Coinductive Calculi, But We Can Explore Them, Internal mobility and agent-passing calculi, Unnamed Item, Fair subtyping for multi-party session types, Unique normal form property of compatible term rewriting systems: A new proof of Chew's theorem, Tree-based generation of languages of fractals, Combination of constraint systems II: Rational amalgamation, Uniform Inductive Reasoning in Transitive Closure Logic via Infinite Descent, Type Inference by Coinductive Logic Programming, Probabilistic Analysis of Binary Sessions, Solving Algebraic Equations Using Coalgebra, CPO-models for second order lambda calculus with recursive types and subtyping, Infinitary affine proofs, Subtyping constrained types, On projecting processes into session types, Variétés d'automates descendants d'arbres infinis, Unification for infinite sets of equations between finite terms, The translation power of top-down tree-to-graph transducers, Axiomatisations of functional dependencies in the presence of records, lists, sets and multisets, Model-100: specification language for interacting processes, Type inference for record concatenation and subtyping, Semantics of infinite tree logic programming, An algebraic semantics approach to the effective resolution of type equations, On flowchart theories. I. The deterministic case, Equivalences and transformations of regular systems - applications to recursive program schemes and grammars, Algebraic solutions to recursion schemes, Static correctness of hierarchical procedures, Unification of kinded infinite trees, C-tree systolic automata, Regular behaviours with names: on rational fixpoints of endofunctors on nominal sets, A first-order axiomatization of the theory of finite trees, Recursive Program Schemes and Context-Free Monads, Deciding implication for functional dependencies in complex-value databases, The category-theoretic solution of recursive program schemes, Enhancing expressivity of checked corecursive streams, Contributions to the semantics of logic perpetual processes, Non-well-founded trees in categories, On inductive inference of cyclic structures, Unification and combination of a class of traversal strategies made with pattern matching and fixed-points, A Mechanized Theory of Regular Trees in Dependent Type Theory, Regularity Equals Monadic Second-Order Definability for Quasi-trees, The equational logic of fixed points, Situated simplification, Unification of infinite sets of terms schematized by primal grammars, Event structure semantics for multiparty sessions, Typed path polymorphism, A note on ordinal DFAs, Query efficient implementation of graphs of bounded clique-width, On second-order iterative monads, A characterisation of deterministic context-free languages by means of right-congruences, Semantics for logic programs without occur check, Weighted graphs: A tool for studying the halting problem and time complexity in term rewriting systems and logic programming, Semantics of types for database objects, Clique-width of countable graphs: A compactness property., A Light Modality for Recursion, Context-Free Session Type Inference, Recursion over realizability structures, A semantics for complex objects and approximate answers, Generalized automata on infinite trees and Muller-McNaughton's theorem, Commutative rational term rewriting, Do judge a test by its cover. Combining combinatorial and property-based testing, Contraction algebras and unification of (infinite) terms, \(\pi\)-calculus, internal mobility, and agent-passing calculi, The monadic second-order logic of graphs. IX: Machines and their behaviours, Idealized coinductive type systems for imperative object-oriented programs, Infinite normal forms for non-linear term rewriting systems, Interpretations of recursively defined types, Average-case analysis of unification algorithms, Infinite hypergraphs. II: Systems of recursive equations, Composition and decomposition of multiparty sessions, Unnamed Item, Picture deformation, The modular decomposition of countable graphs. Definition and construction in monadic second-order logic, Sturmian trees, A new method for undecidability proofs of first order theories, Completely iterative algebras and completely iterative monads, Infinitary combinatory reduction systems, Infinite labeled trees: from rational to Sturmian trees, Contract-based discovery of Web services modulo simple orchestrators, On the existence of nonterminating queries for a restricted class of PROLOG-clauses, Automata on infinite objects and their applications to logic and programming, A type checking algorithm for concurrent object protocols, Abstract Compilation of Object-Oriented Languages into Coinductive CLP(X): Can Type Inference Meet Verification?, On algebras with effectful iteration, Categorical Büchi and parity conditions via alternating fixed points of functors, Bases for parametrized iterativity, Applications and extensions of context-sensitive rewriting, A New Foundation for Finitary Corecursion, ALGEBRAIC LINEAR ORDERINGS, A new foundation for finitary corecursion and iterative algebras, Quantifier elimination for infinite terms, Infinite hypergraphs. I: Basic properties, Type inference with recursive types: Syntax and semantics, How to win a game with features, The solutions of two star-height problems for regular trees, Regular sets over extended tree structures, On the logic of unification, Equational logic of circular data type specification, Coalgebraic Monads, Induction, Coinduction, and Adjoints, The ordinal generated by an ordinal grammar is computable, A Mezei-Wright theorem for categorical algebras, Iterative factor algebras and induced metrics, \(L(A)=L(B)\)? decidability results from complete formal systems, Integrating induction and coinduction via closure operators and proof cycles, Macro tree transducers, attribute grammars, and MSO definable tree translations., Simplifying subtyping constraints: a theory, 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, Satisfying subtype inequalities in polynomial space, A short scientific biography of Maurice Nivat, A coinductive completeness proof for the equivalence of recursive types, Output string languages of compositions of deterministic macro tree transducers

Cites Work