Catálogo de publicaciones - libros

In this paper we define a model of randomly generated databases and show how one can compute the threshold functions for queries expressible in monotone non-recursive datalog. We also show that monotone non-recursive datalog cannot express any property with a sharp threshold. Finally, we show that non-recursive datalog has a 0–1 law for a large class of probability functions, defined in the paper.

An instance of a constraint satisfaction problem is -consistent if any constraints of it can be simultaneously satisfied. For a set Π of constraint types, (Π) denotes the largest ratio of constraints which can be satisfied in any -consistent instance composed by constraints from the set Π. We study the asymptotic behavior of (Π) for sets Π consisting of Boolean predicates.

We study simple greedy approximation algorithms for general class of integer packing problems. We provide a novel analysis based on the duality theory of linear programming. This enables to significantly improve on the approximation ratios of these greedy methods, and gives a unified analysis of greedy for many packing problems. We show matching lower bounds on the ratios of such greedy methods. Applications to some specific problems, including mechanism design for combinatorial auctions, are also shown.

In the maximum solution equation problem a collection of equations are given over some algebraic structure. The objective is to find an assignment to the variables in the equations such that all equations are satisfied and the sum of the variables is maximised. We give tight approximability results for the maximum solution equation problem when the equations are given over groups of the form , where is prime. We also prove that the weighted and unweighted versions of this problem have equal approximability thresholds. Furthermore, we show that the problem is equally hard to solve even if each equation is restricted to contain at most three variables and solvable in polynomial time if the equations are restricted to contain at most two variables. All of our results also hold for a generalised version of maximum solution equation where the elements of the group are mapped arbitrarily to non-negative integers in the objective function.

This paper analyzes the computational complexity of the model checking problem for Higher Order Fixpoint Logic – the modal -calculus enriched with a typed -calculus. It is hard for every level of the elementary time/space hierarchy and in elementary time/space when restricted to formulas of bounded type order.

We consider the problem of job scheduling on a variable voltage processor with discrete voltage/speed levels. We give an algorithm which constructs a minimum energy schedule for jobs in (log ) time. Previous approaches solve this problem by first computing the optimal continuous solution in () time and then adjusting the speed to discrete levels. In our approach, the optimal discrete solution is characterized and computed directly from the inputs. We also show that (log ) time is required, hence the algorithm is optimal for fixed .

The word problem for inverse monoids generated by a set Γ subject to relations of the form = , where and are both idempotents in the free inverse monoid generated by Γ, is investigated. It is shown that for every fixed monoid of this form the word problem can be solved in polynomial time which solves an open problem of Margolis and Meakin. For the uniform word problem, where the presentation is part of the input, EXPTIME-completeness is shown. For the Cayley-graphs of these monoids, it is shown that the first-order theory with regular path predicates is decidable. Regular path predicates allow to state that there is a path from a node to a node that is labeled with a word from some regular language. As a corollary, the decidability of the generalized word problem is deduced. Finally, it is shown that the Cayley-graph of the free inverse monoid has an undecidable monadic second-order theory.

Effective fractal dimension was defined by Lutz (2003) in order to quantitatively analyze the structure of complexity classes. Interesting connections of effective dimension with information theory were also found, in fact the cases of polynomial-space and constructive dimension can be precisely characterized in terms of Kolmogorov complexity, while analogous results for polynomial-time dimension haven’t been found.

In this paper we remedy the situation by using the natural concept of reversible time-bounded compression for finite strings. We completely characterize polynomial-time dimension in terms of polynomial-time compressors.

We compare the expressive power of two automata-based finite-state models of concurrency. We show that Droste’s and Kuske’s coherent stably concurrent automata and Bednarczyk’s forward-stable asynchronous systems describe the same class of regular event structures. This connection subsumes a previous study by Schmitt which relates Stark’s trace automata to asynchronous systems. This work relies on Zielonka’s theorem and some unrecognized result due to Arnold.

This paper addresses an algebraic problem which arises from our study on the information dynamics of cellular automata (CA). The state set of a cell is assumed to be a polynomial ring [] modulo – over a finite field GF(), where is the indeterminate called the information variable. When a CA starts with an initial configuration containing a cell with state , the information of is transmitted to neighboring cells by cellular computation. In such a computation, every cell of a global configuration takes a polynomial in []. Generally denote such a configuration by and let be the set of polynomials appearing in . Our problem is to ask of is contained by . For we define the () = log|〈 〉|, where 〈 〉 is the subring of [] generated by and investigate its relation to the () introduced before. We note here that () =  − |()|, where |()| is the cardinality of the value set of . Then, we prove that () and in turn that () + () = . This result suggests that the computation of the size of subrings is reduced to that of the value size, which is executed much easier than subring generation.