Publications associées à Décidabilité

When is it safe to run a transactional workload under Read Committed?

The popular isolation level multiversion Read Committed (RC) exchanges some of the strong guarantees of serializability for increased transaction throughput. Nevertheless, transaction workloads can sometimes be executed under RC while still guaranteeing se ...

ASSOC COMPUTING MACHINERY2023

Equivalence Checking for Orthocomplemented Bisemilattices in Log-Linear Time

Viktor Kuncak, Simon Guilloud

We present a quasilinear time algorithm to decide the word problem on a natural algebraic structures we call orthocomplemented bisemilattices, a subtheory of boolean algebra. We use as a base a variation of Hopcroft, Ullman and Aho algorithm for tree isomo ...

Springer2022

On Polynomial Algorithms for Normalizing Formulas

Viktor Kuncak, Simon Guilloud, Mario Bucev

We propose a new approach for normalization and simplification of logical formulas. Our approach is based on algorithms for lattice-like structures. Specifically, we present two efficient algorithms for computing a normal form and deciding the word problem ...

2022

A PCP Theorem for Interactive Proofs and Applications

Alessandro Chiesa

The celebrated PCP Theorem states that any language in NP can be decided via a verifier that reads O(1) bits from a polynomially long proof. Interactive oracle proofs (IOP), a generalization of PCPs, allow the verifier to interact with the prover for multi ...

SPRINGER INTERNATIONAL PUBLISHING AG2022

Towards Reliable Evaluation of Algorithms for Road Network Reconstruction from Aerial Images

Pascal Fua, Mateusz Kozinski, Leonardo Citraro

Existing connectivity-oriented performance measures rank road delineation algorithms inconsistently, which makes it difficult to decide which one is best for a given application. We show that these inconsistencies stem from design flaws that make the metri ...

2020

Retaining data from streams of social platforms with minimal regret

Quoc Viet Hung Nguyen, Thành Tâm Nguyên, Chi Thang Duong

Today's social platforms, such as Twitter and Facebook, continuously generate massive volumes of data. The resulting data streams exceed any reasonable limit for permanent storage, especially since data is often redundant, overlapping, sparse, and generall ...

2017

Synthesizing efficient systems in probabilistic environments

Barbara Jobstmann, David Parker

We present a formalism, algorithms and tools to synthesise reactive systems that behave efficiently, i.e., which achieve an optimal trade-off between a given cost and reward model. Synthesis aims to automatically generate a program from a specification. Mo ...

Springer2016

Towards Automating Grammar Equivalence Checking

Viktor Kuncak, Mikaël Mayer, Ravichandhran Kandhadai Madhavan

We consider from practical perspective the (generally undecidable) problem of checking equivalence of context-free grammars. We present both techniques for proving equivalence, as well as techniques for finding counter-examples that establish non-equivalen ...

2015

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.

Décidabilité

Decision Procedures for Power Structures

When is it safe to run a transactional workload under Read Committed?

Equivalence Checking for Orthocomplemented Bisemilattices in Log-Linear Time

On Polynomial Algorithms for Normalizing Formulas

A PCP Theorem for Interactive Proofs and Applications

Towards Reliable Evaluation of Algorithms for Road Network Reconstruction from Aerial Images

Retaining data from streams of social platforms with minimal regret

Undecidability through Fourier series

Synthesizing efficient systems in probabilistic environments

Towards Automating Grammar Equivalence Checking

Graph Chatbot

Chattez avec Graph Search

Towards Automating Grammar Equivalence Checking

Undecidability through Fourier series

Synthesizing efficient systems in probabilistic environments

A PCP Theorem for Interactive Proofs and Applications

Equivalence Checking for Orthocomplemented Bisemilattices in Log-Linear Time

Towards Reliable Evaluation of Algorithms for Road Network Reconstruction from Aerial Images

When is it safe to run a transactional workload under Read Committed?

Retaining data from streams of social platforms with minimal regret