Wyniki wyszukiwania - BazTech

Ograniczanie wyników

Znaleziono wyników: 2

Liczba wyników na stronie

Wyniki wyszukiwania

Sortuj według:

Ogranicz wyniki do:

Unfoldings and Coverings of Weighted Graphs

Courcelle Bruno

Fundamenta Informaticae

2022

Vol. 189, nr 1.

1--47

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.

Order-theoretic Trees : Monadic Second-order Descriptions and Regularity

Courcelle Bruno

Fundamenta Informaticae

2022

Vol. 186, nr 1-4

89--120

An order-theoretic forest is a countable partial order such that the set of elements larger than any element is linearly ordered. It is an order-theoretic tree if any two elements have an upper-bound. The order type of a branch can be any countable linear order. Such generalized infinite trees yield convenient definitions of the rank-width and the modular decomposition of countable graphs. We define an algebra based on only four operations that generate up to isomorphism and via infinite terms these order-theoretic trees and forests. We prove that the associated regular objects, those defined by regular terms, are exactly the ones that are the unique models of monadic second-order sentences.