Catálogo de publicaciones - libros

We start investigating set algebras from a knowledge theoretical point of view. To this end, we suit hybrid logic to the context of knowledge. The common modal approach is extended in this way, which gives us the necessary expressive power. The main issues of the paper are a completeness and a decidability result for the arising logic of knowledge on algebras.

A partial information algorithm for a language computes, for some fixed , for input words , ..., a set of bitstrings containing (,...,). E.g., p-selective, approximable, and easily countable languages are defined by the existence of polynomial-time partial information algorithms of specific type. Self-reducible languages, for different types of self-reductions, form subclasses of PSPACE.

For a self-reducible language , the existence of a partial information algorithm sometimes helps to place into some subclass of PSPACE. The most prominent known result in this respect is: P-selective languages which are self-reducible are in P [9].

Closely related is the fact that the existence of a partial information algorithm for simplifies the type of reductions or self-reductions to . The most prominent known result in this respect is: Turing reductions to easily countable languages simplify to truth-table reductions[8].

We prove new results of this type. We show:

Structural complexity.

We consider the complexity of infinite games played on finite graphs. We establish a framework in which the expressiveness and succinctness of different types of winning conditions can be compared. We show that the problem of deciding the winner in Muller games is PSPACE-complete. This is then used to establish PSPACE-completeness for Emerson-Lei games and for games described by Zielonka DAGs. Adaptations of the proof show PSPACE-completeness for the emptiness problem for Muller automata as well as the model-checking problem for such automata on regular trees. We also show co-NP-completeness for two classes of union-closed games: games specified by a basis and superset Muller games.

The traditional theory of relations (i.e. ) is enriched by adding the formal concept of and . Various possible axioms and their roles are discussed. An approach is focused on application to model software structures.

The online squarefree recognition problem is to detect the first occurrence of a square in a string whose characters are provided as input one at a time. We present an efficient algorithm to solve this problem for strings over arbitrarily ordered alphabets. Its running time is ( log ), where is the ending position of the first square, which matches the running times of the fastest known algorithms for the analogous offline problem. We also present a very simple algorithm for a dynamic version of the problem over general alphabets in which we are initially given a squarefree string, followed by a series of updates, and the objective is to determine after each update if the resulting string contains a square and if so, report it and stop.

Restarting automata are a restricted model of computation that is motivated by the so-called . A computation of a restarting automaton consists of a sequence of cycles such that in each cycle the automaton performs exactly one rewrite step, which replaces a small part of the tape content by another, even word. Here we consider a natural generalization of this model, called , where we require that there exists a such that each rewrite step decreases the weight of the tape content with respect to that function. While it is still unknown whether the two most general types of restarting automata, the RWW-automaton and the RRWW-automaton, differ in their expressive power, we will see that the classes of languages accepted by the shrinking RWW-automaton and the shrinking RRWW-automaton coincide. Further, we will relate shrinking RRWW-automata to finite-change automata, which leads to new insights into the relationships between the classes of languages characterized by (shrinking) restarting automata and some well-known time and space complexity classes.

We prove that every nondeterministic finite automaton with states has an equivalent nondeterministic finite automaton with at most () states. We also show this bound is exact.

We consider monotone ∨, ∧-formulae of atoms, each of which is a monotone inequality of the form ()≥ over the integers, where for = 1,...,, is a given monotone function and is a given threshold. We show that if the ∨-degree of is bounded by a constant, then for linear, transversal and polymatroid monotone inequalities all minimal integer vectors satisfying can be generated in incremental quasi-polynomial time. In contrast, the enumeration problem for the disjunction of inequalities is NP-hard when is part of the input. We also discuss some applications of the above results in disjunctive programming, data mining, matroid and reliability theory.

For many problems, the investigation of their parameterized complexity provides an interesting and useful point of view. The most obvious natural parameterization for the maximum satisfiability problem—the number of satisfiable clauses—makes little sense, because at least half of the clauses can be satisfied in any formula. We look at two optimization variants of the exact satisfiability problem, where a clause is only said to be fulfilled iff exactly one of its literals is set to . Interestingly, these variants behave quite differently. In the case of , where over-satisfied clauses are entirely forbidden, we show fixed parameter tractability. On the other hand, if we choose to ignore over-satisfied clauses, the problem is obtained. Surprisingly, it is W[1]-complete. Still, restricted variants of the problem turn out to be tractable.

For a string =... , a (,), 1≤ <≤ , transforms the string into a string ′=... ... ... , that is, the reversal (,) reverses the order of symbols in the substring ... of . In a case of signed strings, where each symbol is given a sign + or –, the reversal operation also flips the sign of each symbol in the reversed substring. Given two strings, and , signed or unsigned, (SBR) is the problem of finding the minimum number of reversals that transform the string into the string .

Traditionally, the problem was studied for permutations, that is, for strings in which every symbol appears exactly once. We consider a generalization of the problem, -SBR, and allow each symbol to appear at most times in each string, for some ≥ 1. The main result of the paper is a simple ()-approximation algorithm running in time ( · ). For instances with , this is the best known approximation algorithm for -SBR and, moreover, it is faster than the previous best approximation algorithm. In particular, for =(1) which is of interest for DNA comparisons, we have a linear time (1)-approximation algorithm.