Paper Info
Title
On infinite transition graphs having a decidable monadic theory
Abstract
We define a family of graphs whose monadic theory is (in linear space) reducible to the monadic theory S2S of the complete ordered binary tree. This family contains strictly the context-free graphs investigated by Muller and Schupp, and also the equational graphs defined by Courcelle. Using words as representations of vertices, we give a complete set of representatives by prefix rewriting of rational languages. This subset of possible representatives is a boolean algebra preserved by transitive closure of arcs and by rational restriction on vertices.
Year
DOI
Venue
2003
10.1016/S0304-3975(01)00089-5
ICALP
Keywords
DocType
Volume
binary tree,transitive closure
Journal
290
Issue
ISSN
Citations 
1
0304-3975
97
PageRank 
References 
Authors
5.39
12
1
Name
Order
Citations
PageRank
Didier Caucal147039.15