Catálogo de publicaciones - libros

State-based systems and modal logics for reasoning about them often heterogeneously combine a number of features such as non-determinism and probabilities. Here, we show that the combination of features can be reflected algorithmically and develop modular decision procedures for heterogeneous modal logics. The modularity is achieved by formalising the underlying state-based systems as multi-sorted coalgebras and associating both a logical and an algorithmic description to a number of basic building blocks. Our main result is that logics arising as combinations of these building blocks can be decided in polynomial space provided that this is the case for the components. By instantiating the general framework to concrete cases, we obtain decision procedures for a wide variety of structurally different logics, describing e.g. Segala systems and games with uncertain information.

In this paper we present the theory and practice of (co-LP for brevity), a paradigm that combines both inductive and coinductive logic programming. Co-LP is a natural generalization of logic programming and coinductive logic programming, which in turn generalizes other extensions of logic programming, such as infinite trees, lazy predicates, and concurrent communicating predicates. Co-LP has applications to rational trees, verifying infinitary properties, lazy evaluation, concurrent LP, model checking, bisimilarity proofs, etc.

We introduce an offline precomputation technique for mix-nets that drastically reduces the amount of online computation needed. Our method can be based on any additively homomorphic cryptosystem and is applicable when the number of senders and the maximal bit-size of messages are relatively small.

Broadcast encryption schemes enable senders to efficiently broadcast ciphertexts to a large set of receivers in a way that only non-revoked receivers can decrypt them. Black-box traitor revocable broadcast encryption schemes are broadcast encryption schemes that enable a tracer, who is given a pirate decoder, to identify traitors by black-box accessing the given pirated decoder and to revoke traitors so identified. In this paper, we propose a fully collusion resistant black-box traitor revocable broadcast encryption scheme in which the size of each private key is constant, the size of the public key is proportional to the number of receivers, and the sizes of ciphertexts are sub-linear with respect to the number of receivers. The encryption procedure in our scheme requires only a public key. The tracing procedure in it requires only a public key and black-box access to a resettable pirate decoder. The security of our scheme is proved in the generic bilinear group model if the subgroup decision assumption holds.

Various methods have been used to represent a tree of nodes in essentially the information-theoretic minimum space while supporting various navigational operations in constant time, but different representations usually support different operations. Our main contribution is a succinct representation of ordinal trees, based on that of Geary et al. (7), that supports all the navigational operations supported by various succinct tree representations while requiring only 2 + () bits. It also supports efficient level-order traversal, a useful ordering previously supported only with a very limited set of operations (8).

Our second contribution expands on the notion of a single succinct representation supporting more than one traversal ordering, by showing that our method supports two other encoding schemes as abstract data types. In particular, it supports extracting a word ( bits) of the balanced parenthesis sequence (11) or depth first unary degree sequence (3;4) in (()) time, using at most /() + () additional bits, for any () in and (1).

We present a framework to dynamize succinct data structures, to encourage their use over non-succinct versions in a wide variety of important application areas. Our framework can dynamize most state-of-the-art succinct data structures for dictionaries, ordinal trees, labeled trees, and text collections. Of particular note is its direct application to XML indexing structures that answer queries [2]. Our framework focuses on achieving information-theoretically optimal space along with near-optimal update/query bounds.

As the main part of our work, we consider the following problem central to text indexing: Given a text  over an alphabet , construct a compressed data structure answering the queries (), (), and () for a symbol  ∈ . Many data structures consider these queries for static text  [5,3,16,4]. We build on these results and give the best known query bounds for the dynamic version of this problem, supporting arbitrary insertions and deletions of symbols in .

Specifically, with an amortized update time of (), any static succinct data structure  for , taking () time for queries, can be converted by our framework into a dynamic succinct data structure that supports (), (), and () queries in (() + loglog) time, for any constant > 0. When || = polylog(n), we achieve (1) query times. Our update/query bounds are near-optimal with respect to the lower bounds from [13].

Given string  = [1,...,], the problem is to lexicographically sort the suffixes [,...,] for all . This problem is central to the construction of suffix arrays and trees with many applications in string processing, computational biology and compression. A bottleneck in these applications is the amount of needed to perform suffix sorting beyond the space needed to store the input as well as the output. In particular, emphasis is even on the constant in the () =  space algorithms known for this problem,

Currently the best previous result [5] takes time and extra space, for any for strings from a general alphabet. We improve this and present the first known in-place suffix sorting algorithm. Our algorithm takes time using (1) workspace and is optimal in the worst case for the general alphabet.

We systematically investigate the computational complexity of constraint satisfaction problems for constraint languages over an infinite domain. In particular, we study a generalization of the wellestablished notion of from finite to infinite domains. If the constraint language can be defined with an ù-categorical structure, then maximal constraint languages are in one-to-one correspondence to minimal oligomorphic clones. Based on this correspondence, we derive general tractability and hardness criteria for the corresponding constraint satisfaction problems.

We study the definability of constraint satisfaction problems (CSP) in various fixed-point and infinitary logics. We show that testing the solvability of systems of equations over a finite Abelian group, a tractable CSP that was previously known not to be definable in Datalog, is not definable in an infinitary logic with counting and hence that it is not definable in least fixed point logic or its extension with counting. We relate definability of CSPs to their classification obtained from tame congruence theory of the varieties generated by the algebra of polymorphisms of the template structure. In particular, we show that if this variety admits either the unary or affine type, the corresponding CSP is not definable in the infinitary logic with counting. We also study the complexity of determining whether a CSP omits unary and affine types.

We study the boundedness problem for monadic least fixed points as a decision problem. While this problem is known to be undecidable in general and even for syntactically very restricted classes of underlying first-order formulae, we here obtain a decidability result for the boundedness issue for monadic fixed points over arbitrary first-order formulae in restriction to acyclic structures.