Catálogo de publicaciones - libros

Systems of language equations of the form {(, ..., ) = ∅, (, ..., )≠∅} are studied, where , may contain set-theoretic operations and concatenation; they can be equivalently represented as strict inequalities (, ..., ) ⊂ . It is proved that the problem whether such an inequality has a solution is Σ-complete, the problem whether it has a unique solution is in (Σ ∩ Π) ∖ (Σ ∪ Π), the existence of a regular solution is a Σ-complete problem, while testing whether there are finitely many solutions is Σ-complete. The class of languages representable by their unique solutions is exactly the class of recursive sets, though a decision procedure cannot be algorithmically constructed out of an inequality, even if a proof of solution uniqueness is attached.

In recent years the collective tokens philosophy for Petri Nets has gained again the stage, but it is commonly set in opposition to the individual tokens philosophy. In this paper we investigate what can be an adequate event structures to capture the collective tokens philosophy of nets when inhibitor arcs are taken into account.

The three domatic number problem asks whether a given undirected graph can be partitioned into at least three dominating sets, i.e., sets whose closed neighborhood equals the vertex set of the graph. Since this problem is NP-complete, no polynomial-time algorithm is known for it. The naive deterministic algorithm for this problem runs in time 3, up to polynomial factors. In this paper, we design an exact deterministic algorithm for this problem running in time 2.9416. Thus, our algorithm can handle problem instances of larger size than the naive algorithm in the same amount of time. We also present another deterministic and a randomized algorithm for this problem that both have an even better performance for graphs with small maximum degree.

Due to extensive research on tree-width for undirected graphs and due to its many applications in various fields it has been a natural desire for many years to generalize the idea of tree decomposition to directed graphs, but since many parameters in tree-width behave very differently in the world of digraphs, the generalization is still in its preliminary steps.

In this paper, after surveying the main work that has been done on this topic, we propose a new simple definition for directed tree-width and prove a special case of the min-max theorem (duality theorem) relating haven order, bramble number, and tree-width on digraphs. We also compare our definition with previous definitions and study the behavior of some tree-width like parameters such as brambles and havens on digraphs.

Let be a real number with 1 < < 2. We prove that the language of the -shift is Δ iff is a Δ-real. The special case where is 1 is the independently interesting result that the language of the -shift is decidable iff is a computable real. The “if” part of the proof is non-constructive; we show that for Walters’ version of the -shift, no constructive proof exists.

The logic of equality and uninterpreted functions (EUF) has been proposed for processor verification. This paper presents a new data structure called Binary Decision Diagrams for representing EUF formulas (EUF-BDDs). We define EUF-BDDs similar to BDDs, but we allow equalities between terms as labels instead of Boolean variables. We provide an approach to build a reduced ordered EUF-BDD (EUF-ROBDD) and prove that every path to a leaf is satisfiable by construction. Moreover, EUF-ROBDDs are logically equivalent representations of EUF-formulae, so they can also be used to represent state spaces in symbolic model checking with data.

This paper deals with balanced leaf language complexity classes, introduced independently in [1] and [14]. We propose the seed concept for leaf languages, which allows us to give “short” representations for leaf words. We then use seeds to show that leaf languages with  ⊆ () cannot be polylog-sparse (i.e. ∈ (log)), unless collapses.

We also generalize balanced ≤-reductions, which were introduced in [6], to other bit-reductions, for example (balanced) truth-table- and Turing-bit-reductions. Then, similarly to above, we prove that and Σ cannot have polylog-sparse hard sets under those balanced truth-table- and Turing-bit-reductions, if the polynomial-time hierarchy is infinite.

Given a set of strings = {,..., }, the problem asks for the shortest string which contains each as a substring. We consider two measures of success in this problem: the measure, which is the length of , and the measure, which is the difference between the sum of lengths of the and the length of . Both the length and the compression versions of the problem are known to be MAX-SNP-hard. The only explicit approximation ratio lower bounds are by Ott: 1.000057 for the length measure and 1.000089 for the compression measure. Using a natural construction we improve these lower bounds to 1.00082 for the length measure and 1.00093 for the compression measure. Our lower bounds hold even for instances in which the strings are over a binary alphabet and have equal lengths. In fact, we show a somewhat surprising result, that the Shortest Superstring problem (with respect to both measures) is as hard to approximate on instances over a binary alphabet, as it is over any alphabet.

We study Boolean grammars. We introduce stratified semantics for Boolean grammars. We show, how to check, if a Boolean grammar generates a language according to this semantics. We show, that stratified semantics covers a class of important and natural languages. We introduce a recognition algorithm for Boolean grammars compliant to this semantics.