Concept
Recursively enumerable language
Publications associées (17)
A PCP Theorem for Interactive Proofs and Applications
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 AG2022Lower Bounds for Unambiguous Automata via Communication Complexity
Mika Tapani Göös, Weiqiang Yuan
We use results from communication complexity, both new and old ones, to prove lower bounds for unambiguous finite automata (UFAs). We show three results. 1) Complement: There is a language L recognised by an n-state UFA such that the complement language ...
Schloss Dagstuhl - Leibniz-Zentrum für Informatik2022Enumeration of reversible functions and its application to circuit complexity
Giovanni De Micheli, Mathias Soeken, Nabila Abdessaied
We review combinational results to enumerate and classify reversible functions and investigate the application to circuit complexity. In particularly, we consider the effect of negating and permuting input and output variables and the effect of applying li ...
Springer2016Programming with Enumerable Sets of Structures
Viktor Kuncak, Ivan Kuraj, Daniel Jackson
We present an efficient, modular, and feature-rich framework for automated generation and validation of complex structures, suitable for tasks that explore a large space of structured values. Our framework is capable of exhaustive, incremental, parallel, a ...
Assoc Computing Machinery2015Moment Semantics for Reversible Rule-Based Systems
We develop a notion of stochastic rewriting over marked graphs – i.e. directed multigraphs with degree constraints. The approach is based on double-pushout (DPO) graph rewriting. Marked graphs are expressive enough to internalize the ‘no-dangling-edge’ con ...
Springer International Publishing2015Recursive analysis of singular ordinary differential equations
We investigate systems of ordinary differential equations with a parameter. We show that under suitable assumptions on the systems the solutions are computable in the sense of recursive analysis. As an application we give a complete characterization of the ...
Elsevier2010DBToaster: A SQL Compiler for High-Performance Delta Processing in Main-Memory Databases
We present DBToaster, a novel query compilation framework for producing high performance compiled query executors that incrementally and continuously answer standing aggregate queries using in-memory views. DBToaster targets applications that require effic ...
2009Cooperative Localization for Autonomous Underwater Vehicles
This paper describes an algorithm for distributed acoustic navigation for Autonomous Underwater Vehicles (AUVs). Whereas typical AUV navigation systems utilize pre-calibrated arrays of static transponders, our work seeks to create a fully mobile network of ...
2009A method for the enumeration of the floppy modes and the calculation of the associated entropy
We present a method that is based on the Ladd-Frenkel (LF) thermodynamic integration for the study of the rigidity of networks of particles bonded together by short-ranged square well attractive potentials. We show that, by taking the limit of the attracti ...
2008Undecidable propositions by ODE's
The authors define a family of functions by starting with (complex) exponentials and closing under some basic algebraic operations, integration, and solution of certain systems of differential equations. They then show that for every recursively (computabl ...
2007