Automata-based representations for infinite graphs. (English) Zbl 0997.05067
The authors investigate the representation of infinite graphs with the help of finite automata. In their approach, vertices are represented by a regular prefix-free language. Edges are represented by a regular language and a function over tuples. The following three functions are considered: (i) the first difference, (ii) the suffix, and (iii) its infixes. It turns out that the first difference is unsatisfactory for infinite graphs. So the authors deal with representations which use the suffix function and the infixes function. They show that the classes of suffix-representable graphs and infix-representable graphs are strictly larger than the class of equational graphs (introduced by Courcelle) and the class of simple graphs (introduced by Caucal). They compare their two graph classes and they note that the monadic second-order theories of the two graph classes are undecidable (in contrast to the decidability of the monadic second-order theory of the class of simple graphs). They also show that many interesting graph properties can be decided in their two graph classes.
Reviewer: Martin Weese (Potsdam)
MSC:
| 05C62 | Graph representations (geometric and intersection representations, etc.) |
| 68Q45 | Formal languages and automata |
| 03D05 | Automata and formal grammars in connection with logical questions |
| 68R10 | Graph theory (including graph drawing) in computer science |
Keywords:
formal languages; representation of infinite graphs; finite automata; equational graphs; graph classesReferences:
| [1] | S. Arnborg , J. Lagergren and D. Seese , Easy problems for tree-decomposable graphs . J. Algorithms 12 ( 1991 ) 308 - 340 . MR 1105479 | Zbl 0734.68073 · Zbl 0734.68073 · doi:10.1016/0196-6774(91)90006-K |
| [2] | K. Barthelmann , When Can an Equational Simple Graph Be Generated by Hyperedge Replacement ?, in Proc. of the 23th International Symposium on Mathematical Foundations of Computer Science (MFCS’98), edited by L. Brim, J. Gruska and J. Zlatuska. Brno, Czech Republic, August 24 - 28 , 1998, Lecture Notes in Comput. Sci. 1450 ( 1998 ) 543 - 552 . Zbl 0917.05054 · Zbl 0917.05054 |
| [3] | M. Bauderon and B. Courcelle , Graph Expressions and Graph Rewritings . Math. Systems Theory 20 ( 1987 ) 83 - 127 . MR 920770 | Zbl 0641.68115 · Zbl 0641.68115 · doi:10.1007/BF01692060 |
| [4] | H. L. Bodlaender and R. H. Möhring , The pathwidth and treewidth of cographs . SIAM J. Discrete Math. 6 ( 1993 ) 181 - 188 . MR 1215226 | Zbl 0773.05091 · Zbl 0773.05091 · doi:10.1137/0406014 |
| [5] | D. Caucal , On infinite transition graphs having a decidable monadic theory , in Proc. of 23rd International Colloquium on Automata, Languages and Programming (ICALP’96), edited by F.M. auf der Heide and B. Monien. Paderborn, Germany, July 8 - 12 , 1996, Lecture Notes in Comput. Sci. 1099 ( 1996 ) 194 - 205 . Zbl 1045.03509 · Zbl 1045.03509 |
| [6] | D.G. Corneil , H. Lerchs and L. Stuart Burlingham , Complement reducible graphs . Discrete Appl. Math. 3 ( 1981 ) 163 - 174 . MR 619603 | Zbl 0463.05057 · Zbl 0463.05057 · doi:10.1016/0166-218X(81)90013-5 |
| [7] | B. Courcelle , The monadic second-order logic of graphs . II. Infinite graphs of bounded width. Mathematical Systems Theory 21 ( 1989 ) 187 - 221 . MR 987150 | Zbl 0694.68043 · Zbl 0694.68043 · doi:10.1007/BF02088013 |
| [8] | B. Courcelle , The monadic second-order logic of graphs . III. Tree-width, forbidden minors and complexity issues. RAIRO: Theoret. Informatics Appl. 26 ( 1992 ) 257 - 286 . Numdam | MR 1170326 | Zbl 0754.03006 · Zbl 0754.03006 |
| [9] | A. Ehrenfeucht , J. Engelfriet and G. Rozenberg , Finite Languages for the Representation of Finite Graphs . J. Comput. System Sci. 52 ( 1996 ) 170 - 184 . MR 1375812 | Zbl 0846.68080 · Zbl 0846.68080 · doi:10.1006/jcss.1996.0013 |
| [10] | J. Engelfriet , T. Harju , A. Proskurowski and G. Rozenberg , Characterization and Complexity of Uniformly Non-primitive Labeled 2-Structures . Theoretical Comput. Sci. 154 ( 1996 ) 247 - 282 . MR 1369531 | Zbl 0873.68161 · Zbl 0873.68161 · doi:10.1016/0304-3975(94)00272-X |
| [11] | P.C. Fisher , Multi-Tape and Infinite-State Automata - A Survey . Comm. ACM 8 ( 1965 ) 799 - 805 . Zbl 0129.00503 · Zbl 0129.00503 · doi:10.1145/365691.365962 |
| [12] | J. Hopcroft and J. Ullman , Introduction to Automata Theory , Formal Languages and Computation. Addison-Wesley Publishing Company, Addison-Wesley Series in Comput. Sci.( 1979 ) MR 645539 | Zbl 0426.68001 · Zbl 0426.68001 |
| [13] | S. La Torre and M. Napoli , Representing Hyper-Graphs by Regular Languages . in Proc. of the 23th International Symposium on Mathematical Foundations of Computer Science (MFCS’98), edited by L. Brim, J. Gruska and J. Zlatuska, Brno, Czech Republic, August 24 - 28 , 1998, Lecture Notes in Comput. Sci. 1450 ( 1998 ) 571 - 579 . Zbl 0915.05092 · Zbl 0915.05092 |
| [14] | C. Morvan , On Rational Graphs , in Proc. of the 3rd International Conference on Foundations of Software Science and Computation Structures (FOSSACS 2000). Berlin, Germany, March 25 - April 2, 2000, Lecture Notes in Comput. Sci. 1784 ( 2000 ) 252 - 266 . MR 1798632 | Zbl 0961.68107 · Zbl 0961.68107 |
| [15] | N. Robertson and P. Seymour , Graph Minors . II Algorithmic aspects of tree-width. J. Algorithms 7 ( 1986 ) 309 - 322 . MR 855559 | Zbl 0611.05017 · Zbl 0611.05017 · doi:10.1016/0196-6774(86)90023-4 |
| [16] | J. Valdez , R. E. Tarjan and E. Lawler , The recognition of series parallel digraphs . SIAM J. Comput. 11 ( 1982 ) 298 - 313 . MR 652904 | Zbl 0478.68065 · Zbl 0478.68065 · doi:10.1137/0211023 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
