On infinite terms having a decidable monadic theory

DOI10.1007/3-540-45687-2_13MaRDI QIDQ4708567zbMATH OpenFDO

Authors Didier Caucal

Publication date 18 June 2003

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL http://link.springer.de/link/service/series/0558/bibs/2420/24200165.htm

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) Grammars and rewriting systems (68Q42)

Recommendations

• The monadic theory of morphic infinite words and generalizations
• The monadic theory of morphic infinite words and generalizations
• scientific article; zbMATH DE number 2102748
• Deciding monadic theories of hyperalgebraic trees
• On infinite transition graphs having a decidable monadic theory

Cited in

(26)

• The evaluation of first-order substitution is monadic second-order compatible
• On infinite transition graphs having a decidable monadic theory
• The monadic theory of morphic infinite words and generalizations
• Automata on infinite trees
• Shelah-Stupp's and Muchnik's iterations revisited
• The monadic theory of finite representations of infinite words
• Rewriting higher-order stack trees
• Iterated pushdown automata and sequences of rational numbers
• The Caucal hierarchy: interpretations in the (W)MSO+\(\mathsf{U}\) logic
• Rewriting in the partial algebra of typed terms modulo AC
• Model-checking games for typed -calculi
• Isomorphism of regular trees and words
• Rewriting higher-order stack trees
• The Reachability Problem over Infinite Graphs
• A Hierarchy of Automaticω-Words having a Decidable MSO Theory
• When Is Reachability Intrinsically Decidable?
• Model Transformations in Decidability Proofs for Monadic Theories
• On the Boundedness Problem for Higher-Order Pushdown Vector Addition Systems
• Domains for Higher-Order Games
• On the expressive power of higher-order pushdown systems
• Choice functions and well-orderings over the infinite binary tree
• The structure of trees in the pushdown hierarchy
• Logical aspects of Cayley-graphs: the group case
• Automatic structures and the problem of natural well-orderings
• Tree representations of infinite words and their logical properties
• On the structure of graphs in the Caucal hierarchy

This page was built for publication: On infinite terms having a decidable monadic theory

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4708567)