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. We prove
similar statements for unfoldings.
Our study of the difficult proof of Leighton's Theorem lead us to generalize
coverings and similarly, unfoldings, by attaching finite or infinite weights 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 infinite weights provides us
with finite descriptions of regular trees having nodes of countably infinite
degree. We also generalize to weighted graphs and their coverings a classical
factorization theorem of their characteristic polynomials.
In a former paper 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.
We study minimization problems for deterministic $\omega$-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 $\omega$-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.