Unfoldings and Coverings of Weighted Graphs

• Autorzy: Courcelle Bruno

Identyfikatory

DOI

10.3233/FI-222150

• Języki publikacji: EN

Abstrakty

EN

Coverings of undirected graphs are used in distributed computing, and unfoldings of directed graphs in semantics of programs. We study these two notions from a graph theoretical point of view so as to highlight their similarities, as they are both defined in terms of surjective graph homomorphisms. In particular, universal coverings and complete unfoldings are infinite trees that are regular if the initial graphs are finite. Regularity means that a tree has finitely many subtrees up to isomorphism. Two important theorems have been established by Leighton and Norris for coverings of finite graphs. We prove similar results for unfoldings of finite directed graphs. Moreover, we generalize coverings and similarly, unfoldings to graphs and digraphs equipped with finite or infinite weights attached to edges of the covered or unfolded graphs. This generalization yields a canonical "factorization" of the universal covering of any finite graph, that (provably) does not exist without using weights. Introducing ω as an infinite weight provides us with finite descriptions of regular trees having nodes of countably infinite degree. Regular trees (trees having finitely many subtrees up to isomorphism) play an important role in the extension of Formal Language Theory to infinite structures described in finitary ways. Our weighted graphs offer effective descriptions of the above mentioned regular trees and yield decidability results. We also generalize to weighted graphs and their coverings a classical factorization theorem of their characteristic polynomials.

Słowa kluczowe

EN

graph unfolding; graph covering; universal covering; regular tree; weighted graph; characteristic polynomial; graph factorization

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2022
• Tom: Vol. 189, nr 1.
• Strony: 1--47
• Opis fizyczny: Bibliogr. 25 poz.

Twórcy

autor

Courcelle Bruno

• LaBRI, CNRS (UMR 5800), University of Bordeaux, France

Bibliografia

• [1] Abello J, Fellows MR, and Stillwell J. On the complexity and combinatorics of covering finite complexes, Australasian J. Combinatorics, 1991. 4:103-112.
• [2] Angluin D. Local and global properties in networks of processors (extended abstract). Proceedings of Symposium on Theory of Computing, 1980, pp. 82-93
• [3] Angluin D, and Gardiner A. Finite common coverings of pairs of regular graphs, J. of Combinatorial Theory, Series B, 1981. 30(2):184-187. doi:10.1016/0095-8956(81)90062-9.
• [4] Arnold A. Finite transition systems, Prentice-Hall, 1994 (translated by J. Plaice).
• [5] Bass H, and Kulkarni R. Uniform tree lattices, Jour. of the American Math. Society, 1990. 3:843-902. doi:10.2307/1990905.
• [6] Berkholz C, Bonsma P, and Grohe M. Tight lower and upper bounds for the complexity of canonical colour refinement. Proceedings of ESA 2013, Lecture Notes in Computer Science 2013. 8125 pp. 145-156. doi:10.1007/978-3-642-40450-4 13.
• [7] Bodlaender H. The classification of coverings of processor networks. J. Parallel Distrib. Comput. 1989. 6(1):166-182. doi:10.1016/0743-7315(89)90048-8.
• [8] Bodlaender H, and van Leeuwen J. Simulation of large networks on smaller networks. Information and Control 1986. 71(3):143-180. doi:10.1016/S0019-9958(86)80008-0.
• [9] Boldi P, and Vigna S. Fibrations of graphs. Discrete Mathematics. 2002. 243 :21-66. doi:10.1016/S0012-365X(00)00455-6.
• [10] Courcelle B. Fundamental properties of infinite trees. Theor. Comput. Sci. 1983. 25(2):95-169. doi:10.1016/0304-3975(83)90059-2.
• [11] Courcelle B. Recursive applicative program schemes, in Handbook of Theoretical Computer Science, vol. B, Elsevier, 1990, pp. 459-492.
• [12] Courcelle B. The monadic second-order logic of graphs IX: Machines and their behaviours. Theor. Comput. Sci. 1995. 151(1):125-162. doi:10.1016/0304-3975(95)00049-3.
• [13] Courcelle B. Regular and strongly regular infinite trees, 2023, in preparation.
• [14] Courcelle B, and Engelfriet J. Graph structure and monadic second-order logic, a language theoretic approach, Cambridge University Press, 2012. doi:10.1017/CBO9780511977619.
• [15] Courcelle B, and Walukiewicz I. Monadic second-order logic, graph coverings and unfolding’s of transition systems. Ann. Pure Appl. Logic. 1998. 92(1):35-62. doi:10.1016/S0168-0072(97)00048-1.
• [16] Fiala J, and Kratochvıl J. Locally constrained graph homomorphisms - structure, complexity, and applications. Computer Science Review. 2008. 2(2):97-111. doi:10.1016/j.cosrev.2008.06.001.
• [17] Krebs A, and Verbitsky O. Universal covers, color refinement, and two-variable counting logic: Lower bounds for the depth. Proceedings of Logic in Computer Science, 2015, pp. 689-700. doi:10.1109/LICS.2015.69.
• [18] Leighton F. Finite common coverings of graphs. J. Comb. Theory, Ser. B. 1982. 33(3):231-238. doi:10.1016/0095-8956(82)90042-9.
• [19] Mohar B. A common cover of graphs and 2-cell embeddings, J. Comb. Theory, Ser. B. 1986. 40(1):94-106. doi:10.1016/0095-8956(86)90067-5.
• [20] Neumann WD. On Leighton’s graph covering theorem, Groups, Geometry and Dynamics. 2011. 4:863-872.
• [21] Norris N. Universal covers of graphs: Isomorphism to depth n − 1 implies isomorphism to all depths, Discrete Applied Math. 1995. 56(1):61-74. doi:10.1016/0166-218X(93)E0133-J.
• [22] Reidemeister K. Einfühlung in die kombinatorische Topologie, F. Vieweg and Sohn, 1932 (and Springer, 1951)
• [23] Scheinerman E, and Ullman D. Fractional Graph Theory, J. Wiley, 2008, https://www.ams.jhu.edu/ers/wp-content/uploads/2015/12/fgt.pdf.
• [24] Tucker T. Some topological graph theory for topologists: A sampler of covering space construction, in Topology and Combinatorial Group Theory, P. Latiolaids ed., Lec. Notes Maths. Springer 1990 1440:192-207.
• [25] Woodhouse J. Revisiting Leighton’s theorem with the Haar measure, Mathematical Proceedings of the Cambridge Philosophical Society, Cambridge University Press. January 2020, pp. 1-9. doi:10.1017/S0305004119000550