Catálogo de publicaciones - libros

Splicing systems are generative devices of formal languages, introduced by Head in 1987 to model biological phenomena on linear and circular DNA molecules. In this paper we introduce a special class of named . We prove that a marked system generates a if and only if satisfies a special (decidable) property. As a consequence, we show that we can decide whether a regular circular language is generated by a marked system and we characterize the structure of these regular circular languages.

We present quantum query complexity bounds for testing algebraic properties. For a set and a binary operation on , we consider the decision problem whether  is a semigroup or has an identity element. If  is a monoid, we want to decide whether  is a group.

We present quantum algorithms for these problems that improve the best known classical complexity bounds. In particular, we give the first application of the new quantum random walk technique by Magniez, Nayak, Roland, and Santha [18] that improves the previous bounds by Ambainis [3] and Szegedy [23]. We also present several lower bounds for testing algebraic properties.

We show that the family of tree languages recognized by weak alternating automata is closed by three set theoretic operations that correspond to sum, multiplication by ordinals < , and pseudo-exponentiation with the base of the Wadge degrees. In consequence, the Wadge hierarchy of weakly recognizable tree languages has the height of at least , that is the least fixed point of the exponentiation with the base .

We give an algorithm for deciding productivity of a large and natural class of recursive stream definitions. A stream definition is called ‘productive’ if it can be evaluated continuously in such a way that a uniquely determined stream is obtained as the limit. Whereas productivity is undecidable for stream definitions in general, we show that it can be decided for ‘pure’ stream definitions. For every pure stream definition the process of its evaluation can be modelled by the dataflow of abstract stream elements, called ‘pebbles’, in a finite ‘pebbleflow net(work)’. And the production of a pebbleflow net associated with a pure stream definition, that is, the amount of pebbles the net is able to produce at its output port, can be calculated by reducing nets to trivial nets.

We study the multi-dimensional version of the bin packing problem with conflicts. We are given a set of squares  = { 1,2, ...,} with sides ,, ..., ∈ [0,1] and a conflict graph  = (,). We seek to find a partition of the items into independent sets of , where each independent set can be packed into a unit square bin, such that no two squares packed together in one bin overlap. The goal is to minimize the number of independent sets in the partition.

This problem generalizes the square packing problem (in which we have  = ∅) and the graph coloring problem (in which  = 0 for all  = 1,2, ...,). It is well known that coloring problems on general graphs are hard to approximate. Following previous work on the one-dimensional problem, we study the problem on specific graph classes, namely, bipartite graphs and perfect graphs.

We design a 2 + -approximation for bipartite graphs, which is almost best possible (unless  = ). For perfect graphs, we design a 3.2744-approximation.

We investigate issues regarding two hard problems related to voting, the optimal weighted lobbying problem and the winner problem for Dodgson elections. Regarding the former, Christian et al. [2] showed that optimal lobbying is intractable in the sense of parameterized complexity. We provide an efficient greedy algorithm that achieves a logarithmic approximation ratio for this problem and even for a more general variant—optimal weighted lobbying. We prove that essentially no better approximation ratio than ours can be proven for this greedy algorithm.

The problem of determining Dodgson winners is known to be complete for parallel access to NP [11]. Homan and Hemaspaandra [10] proposed an efficient greedy heuristic for finding Dodgson winners with a guaranteed frequency of success, and their heuristic is a “frequently self-knowingly correct algorithm.” We prove that every distributional problem solvable in polynomial time on the average with respect to the uniform distribution has a frequently self-knowingly correct polynomial-time algorithm. Furthermore, we study some features of probability weight of correctness with respect to Procaccia and Rosenschein’s junta distributions [15].

In the problem, a graph is to be changed to a disjoint union of cliques by at most operations of or . Improving on the best previously known quadratic-size polynomial-time kernelization, we describe how a crown-type structural reduction rule can be used to obtain a 6 kernelization bound.

We give an answer to a question of Barrington, Beigel and Rudich, asked in 1992, concerning the largest such that the OR function in variables can be weakly represented by a quadratic polynomial modulo 6. More specifically, we show that no 11-variable quadratic polynomial exists that is congruent to zero modulo 6 if all arguments are 0, and non-zero modulo 6 on the set {0,1}, otherwise.

A -king in a directed graph is a node from which each node in the graph can be reached via paths of length at most . Recently, kings have proven useful in theoretical computer science, in particular in the study of the complexity of reachability problems and semifeasible sets. In this paper, we study the complexity of recognizing -kings. For each succinctly specified family of tournaments (completely oriented digraphs), the -king problem is easily seen to belong to . We prove that the complexity of kingship problems is a rich enough vocabulary to pinpoint every nontrivial many-one degree in . That is, we show that for every  ≥ 2 every set in other than ∅ and is equivalent to a -king problem under -reductions. The equivalence can be instantiated via a simple padding function. Our results can be used to show that the radius problem for arbitrary succinctly represented graphs is -complete. In contrast, the diameter problem for arbitrary succinctly represented graphs (or even tournaments) is -complete.

We introduce a notion of hyperbolicity in monoids which is a restriction of that suggested by Duncan and Gilman. One advantage is that the notion gives rise to efficient algorithms for dealing with certain questions; for example, the word problem can be solved in time . We also introduce a new way of defining automatic monoids which provides a uniform framework for the discussion of these concepts.