Concept
Decidability (logic)
Related publications (36)
Decision Procedures for Power Structures
We study the decision problem for the existential fragment of the theory of power structures. We prove complexity results that parallel the decidability results of Feferman-Vaught for the theories of product structures thereby showing that the construction ...
EPFL2023When 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 MACHINERY2023On 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 ...
2022Undecidability through Fourier series
In computability theory a variety of combinatorial systems are encountered (word problems, production systems) that exhibit undecidability properties. Here we seek such structures in the realm of Analysis, more specifically in the area of Fourier Analysis. ...
Elsevier Science Bv2016Towards 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