Fundamenta Informaticae - Volume 189, issue 1

Authors: Courcelle, Bruno

Article Type: Research Article

Abstract: 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 . Show more

Keywords: graph unfolding, graph covering, universal covering, regular tree, weighted graph, characteristic polynomial, graph factorization

DOI: 10.3233/FI-222150

Citation: Fundamenta Informaticae, vol. 189, no. 1, pp. 1-47, 2022

Authors: Kłopotek, Mieczysław A. | Wierzchoń, Sławomir T. | Kłopotek, Robert A.

Article Type: Research Article

Abstract: In a former paper [1] the concept of Bipartite PageRank was introduced and a theorem on the limit of authority flowing between nodes for personalized PageRank has been generalized. In this paper we want to extend those results to multimodal networks. In particular we deal with a hypergraph type that may be used for describing multimodal network where a hyperlink connects nodes from each of the modalities. We introduce a generalisation of PageRank for such graphs and define the respective random walk model that can be used for computations. We state and prove theorems on the limit of outflow of …authority for cases where individual modalities have identical and distinct damping factors. Show more

Keywords: PageRank, random walk, ranking, multimodal networks, social networks, M-uniform M-partite hypegraphs, authority flow bounds

DOI: 10.3233/FI-222151

Citation: Fundamenta Informaticae, vol. 189, no. 1, pp. 49-68, 2022

Authors: Löding, Christof | Stachon, Max Philip

Article Type: Research Article

Abstract: We study minimization problems for deterministic ω-automata in the presence of don’t care words. We prove that the number of priorities in deterministic parity automata can be efficiently minimized under an arbitrary set of don’t care words. We derive that from a more general result from which one also obtains an efficient minimization algorithm for deterministic parity automata with informative right-congruence (without don’t care words). We then analyze languages of don’t care words with a trivial right-congruence. For such sets of don’t care words it is known that weak deterministic Büchi automata (WDBA) have a unique minimal automaton that can …be efficiently computed from a given WDBA (Eisinger, Klaedtke 2006). We give a congruence-based characterization of the corresponding minimal WDBA, and show that the don’t care minimization results for WDBA do not extend to deterministic ω-automata with informative right-congruence: for this class there is no unique minimal automaton for a given don’t care set with trivial right congruence, and the minimization problem is NP-hard. Finally, we extend an active learning algorithm for WDBA (Maler, Pnueli 1995) to the setting with an additional set of don’t care words with trivial right-congruence. Show more

Keywords: deterministic ω-automata, don’t care words, learning, minimization

DOI: 10.3233/FI-222152

Citation: Fundamenta Informaticae, vol. 189, no. 1, pp. 69-91, 2022