Arbeitsgemeinschaft Logik und Automaten

Vorträge im Wintersemester 2005/06

Some Hierarchies and Reducibilities on Regular Languages

Do, 20.10.2005, 14:00 Uhr
Victor Selivanov, Novosibirsk Pedagogical University


We discuss some known and introduce some new hierarchies and reducibilities on regular sets. We establish some facts on the corresponding degree structures and relate the reducibilities to hierarchies. As an application, we characterize regular languages whose leaf-language classes (in the balanced model) are contained in the polynomial hierarchy. For any reducibility we try to give some motivation and interesting open questions, in a hope to show that study of these reducibilities is important for automata theory and computational complexity.
Hypertree Decomposition

Do, 27.10.2005, 14:00 Uhr, Raum 4116
Tobias Ganzow, RWTH Aachen


About five years ago, Gottlob, Leone, and Scarcello introduced the concept of hypertree decomposition of hypergraphs and the corresponding notion of hypertree-width. Their main motivation was to transfer the well-known notion of tree decomposition of graphs, as introduced by Robertson and Seymour, to hypergraphs in a sensible way. In fact, hypertree decompositions share many desirable properties with tree decompositions: The decision problem whether a hypergraph has hypertree-width at most k is in LOGCFL (and thus in P), and many problems that are, in general, NP-complete become tractable when restricted to instances of bounded hypertree-width, e.g. the homomorphism problem, boolean conjunctive query evaluation, and several others.

This talk shall give an overview of various aspects of hypertree decomposition, amongst others a game theoretic characterization of hypertree-width by means of the "Robber and Marshals Game" as well as methods for computing hypertree decompositions, and state some related open problems.

On Decidability of Monadic Logic of Order over the Naturals Expanded by Unary Predicates

Do, 2.3.2006, 14:00 Uhr, Raum 4116
Alexander Rabinovich, Tel Aviv University


We deal with the decidability of monadic second-order theory of the natural numbers expanded by unary predicates. Elgot and Rabin found many interesting unary predicates P such that the monadic theory of {Nat, <, P} is decidable. Their results and techniques have been extended over the years. A class of effectively profinitely ultimately periodic (e.p.u.p.) predicates was introduced. Many examples of e.p.u.p. predicates were provided, and it was shown by Carton and Thomas, that if P is an e.p.u.p. predicate then the monadic theory of {Nat, <, P} is decidable. We show that this is a necessary condition.

Theorem: The monadic second-order theory of {Nat, <, P} is decidable if and only if P is effectively profinitely ultimately periodic.