Paper Info
Title
On Infinite Terms Having a Decidable Monadic Theory
Abstract
We study a transformation on terms consisting of applying an inverse deterministic rational mapping followed by an unfolding. Iterating these transformations from the regular terms gives a hierarchy of families of terms having a decidable monadic theory. In particular, the family at level 2 contains the morphic infinite words investigated by Carton and Thomas. We show that this hierarchy coincides with the hierarchy considered by Knapik, Niwi驴ski and Urzyczyn: the families of terms that are solutions of higher order safe schemes. We also show that this hierarchy coincides with the hierarchy defined by Damm, and recently considered by Courcelle and Knapik: the families of terms obtained by iterating applications of first order substitutions to the set of regular terms. Finally, using second order substitutions yields the same terms.
Year
DOI
Venue
2002
10.1007/3-540-45687-2_13
MFCS
Keywords
Field
DocType
morphic infinite word,higher order,order substitution,infinite terms,decidable monadic theory,safe scheme,inverse deterministic rational mapping,regular term,iterating application,order substitutions yield,first order,second order
Inverse,Discrete mathematics,Combinatorics,Decidability,Rational mapping,Graph rewriting,Hierarchy,Deterministic system (philosophy),Monadic predicate calculus,Monad (functional programming),Mathematics
Conference
Volume
ISSN
ISBN
2420
0302-9743
3-540-44040-2
Citations 
PageRank 
References 
60
2.48
19
Authors
1
Name
Order
Citations
PageRank
Didier Caucal147039.15