Mengel, Stefan Skritek, Sebastian
Published in
Theory of Computing Systems

We study the complexity of evaluating well-designed pattern trees, a query language extending conjunctive queries with the possibility to define parts of the query to be optional. This possibility of optional parts is important for obtaining meaningful results over incomplete data sources as it is common in semantic web settings. Recently, a struct...

Amarilli, Antoine Capelli, Florent Monet, Mikaël Senellart, Pierre
Published in
Theory of Computing Systems

The field of knowledge compilation establishes the tractability of many tasks by studying how to compile them to Boolean circuit classes obeying some requirements such as structuredness, decomposability, and determinism. However, in other settings such as intensional query evaluation on databases, we obtain Boolean circuits that satisfy some width ...

Bergstra, J. A. Middelburg, C. A.
Published in
Theory of Computing Systems

In process algebras such as ACP (Algebra of Communicating Processes), parallel processes are considered to be interleaved in an arbitrary way. In the case of multi-threading as found in contemporary programming languages, parallel processes are actually interleaved according to some interleaving strategy. An interleaving strategy is what is called ...

Castañeda, Armando Delporte-Gallet, Carole Fauconnier, Hugues Rajsbaum, Sergio Raynal, Michel
Published in
Theory of Computing Systems

When considering distributed computing, reliable message-passing synchronous systems on the one side, and asynchronous failure-prone shared-memory systems on the other side, remain two quite independently studied ends of the reliability/asynchrony spectrum. The concept of locality of a computation is central to the first one, while the concept of w...

Sankowski, Piotr Węgrzycki, Karol

Consider an unweighted, directed graph $G$ with the diameter $D$. In this paper, we introduce the framework for counting cycles and walks of given length in matrix multiplication time $\widetilde{O}(n^\omega)$. The framework is based on the fast decomposition into Frobenius normal form and the Hankel matrix-vector multiplication. It allows us to so...

Gheorghiu, Alexandru Kapourniotis, Theodoros Kashefi, Elham
Published in
Theory of Computing Systems

Quantum computers promise to efficiently solve not only problems believed to be intractable for classical computers, but also problems for which verifying the solution is also considered intractable. This raises the question of how one can check whether quantum computers are indeed producing correct results. This task, known as quantum verification...

Casteigts, Arnaud Klasing, Ralf Neggaz, Yessin M. Peters, Joseph G.
Published in
Theory of Computing Systems

We present a general framework for computing parameters of dynamic networks which are modelled as a sequence G=(G1,G2,…,Gδ)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document...

Balabonski, Thibaut Delga, Amélie Rieg, Lionel Tixeuil, Sébastien Urbain, Xavier
Published in
Theory of Computing Systems

In mobile robotic swarms, the gathering problem consists in coordinating all the robots so that in finite time they occupy the same location, not known beforehand. Multiplicity detection refers to the ability to detect that more than one robot can occupy a given position. When the robotic swarm operates synchronously, a well-known result by Cohen a...

Bramas, Quentin Foreback, Dianne Nesterenko, Mikhail Tixeuil, Sébastien
Published in
Theory of Computing Systems

We assume that a message may be delivered by packets through multiple hops and investigate the feasibility and efficiency of an Omega Failure Detector implementation. To motivate the study, we prove the existence and sustainability of a leader is exponentially more probable in a multi-hop than in a single-hop implementation. An implementation is: m...

Place, Thomas Zeitoun, Marc
Published in
Theory of Computing Systems

In the theory of formal languages, the understanding of concatenation hierarchies of regular languages is one of the most fundamental and challenging topics. In this paper, we survey progress made on this problem since 1971. We also establish new generic statements regarding this problem.