Paper Info
Title
An Internal Presentation of Regular Graphs by Prefix-Recognizable Graphs
Abstract
.    The study of infinite graphs has potential applications in the specification and verification of infinite systems and in the transformation of such systems. Prefix-recognizable graphs and regular graphs are of particular interest in this area since their monadic second-order theories are decidable. Although the latter form a proper subclass of the former, no characterization of regular graphs within the class of prefix-recognizable ones has been known, except for a graph-theoretic one in [2]. We provide here three such new characterizations. In particular, a decidable, language-theoretic, necessary and sufficient condition for the regularity of any prefix-recognizable graph is established. Our proofs yield a construction of a deterministic hyperedge-replacement grammar for any prefix-recognizable graph that is regular.
Year
DOI
Venue
2001
10.1007/s00224-001-1015-5
Theory Comput. Syst.
Keywords
Field
DocType
Binary Relation,Regular Graph,Regular Language,Graph Grammar,Dependence Level
Discrete mathematics,Random regular graph,Indifference graph,Combinatorics,Modular decomposition,Strongly regular graph,Chordal graph,Graph product,Cograph,Pathwidth,Mathematics
Journal
Volume
Issue
ISSN
34
4
1432-4350
Citations 
PageRank 
References 
6
0.61
20
Authors
2
Name
Order
Citations
PageRank
Didier Caucal147039.15
Teodor Knapik222216.13