Time filter

Source Type

Ameloot T.J.,transnational University of Limburg
ACM Transactions on Database Systems | Year: 2015

A distributed database system often operates in an asynchronous communication model where messages can be arbitrarily delayed. This communication model causes nondeterministic effects like unpredictable arrival orders of messages. Nonetheless, in general we want the distributed system to be deterministic; the system should produce the same output despite the nondeterministic effects on messages. Previously, two interpretations of determinism have been proposed. The first says that all infinite fair computation traces produce the same output. The second interpretation is a confluence notion, saying that all finite computation traces can still be extended to produce the same output. A decidability result for the confluence notion was previously obtained for so-called simple transducer networks, a model from the field of declarative networking. In the current article, we also present a decidability result for simple transducer networks, but this time for the first interpretation of determinism, with infinite fair computation traces. We also compare the expressivity of simple transducer networks under both interpretations. © 2015 ACM.

Brijder R.,transnational University of Limburg | Hoogeboom H.J.,Leiden University
European Journal of Combinatorics | Year: 2014

We provide a unified framework in which the interlace polynomial and several related graph polynomials are defined more generally for multimatroids and delta-matroids. Using combinatorial properties of multimatroids rather than graph-theoretical arguments, we find that various known results about these polynomials, including their recursive relations, are both more efficiently and more generally obtained. In addition, we obtain several interrelationships and results for polynomials on multimatroids and delta-matroids that correspond to new interrelationships and results for the corresponding graph polynomials. As a tool we prove the equivalence of tight 3-matroids and delta-matroids closed under the operations of twist and loop complementation, called vf-safe delta-matroids. This result is of independent interest and related to the equivalence between tight 2-matroids and even delta-matroids observed by Bouchet. © 2014 Elsevier Ltd.

Gelade W.,transnational University of Limburg
Theoretical Computer Science | Year: 2010

In this paper, we study the succinctness of regular expressions (REs) extended with interleaving, intersection and counting operators. We show that in a translation from REs with interleaving to standard regular expressions a double exponential size increase cannot be avoided. We also consider the complexity of translations to finite automata. We give a tight exponential lower bound on the translation of REs with intersection to NFAs, and, for each of the three classes of REs, we show that in a translation to a DFA a double exponential size increase cannot be avoided. Together with known results, this gives a complete picture of the complexity of translating REs extended with interleaving, intersection or counting into (standard) regular expressions, NFAs, and DFAs. © 2010 Elsevier B.V. All rights reserved.

Neven F.,transnational University of Limburg
Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems | Year: 2016

Database research has witnessed a renewed interest for data processing in distributed and parallel settings. While distributed and parallel data management systems have been around for quite some time, it is the rise of cloud computing and the advent of Big Data that presents the community with new challenges. This paper highlights recent research concerning the logical foundations of massively parallel and distributed systems. The first part of the paper concerns massively parallel systems where computation proceeds in a number of synchronized rounds. Here, the focus is on evaluation algorithms for conjunctive queries as well as on reasoning about correctness and optimization of such algorithms. The second part of the paper addresses a distributed asynchronous setting where eventual consistency comes into play. Here, the focus is on coordination-free computation and its relationship to logical monotonicity and Datalog programs.

Brijder R.,transnational University of Limburg | Hoogeboom H.J.,Leiden University
European Journal of Combinatorics | Year: 2011

We study the interplay between the principal pivot transform (pivot) and loop complementation for graphs. This is done by generalizing loop complementation (in addition to pivot) to set systems. We show that the operations together, when restricted to single vertices, form the permutation group S3. This leads, e.g., to a normal form for sequences of pivots and loop complementation on graphs. The results have consequences for the operations of local complementation and edge complementation on simple graphs: an alternative proof of a classic result involving local and edge complementation is obtained, and the effect of sequences of local complementations on simple graphs is characterized. © 2011 Elsevier Ltd.

Discover hidden collaborations