enter search term and/or author name
The Probability of a Computable Output from a Random Oracle
George Barmpalias, Douglas Cenzer, Christopher P. Porter
Article No.: 18
Consider a universal oracle Turing machine that prints a finite or an infinite binary sequence, based on the answers to the binary queries that it makes during the computation. We study the probability that this output is infinite and computable...
This article introduces differential hybrid games, which combine differential games with hybrid games. In both kinds of games, two players interact with continuous dynamics. The difference is that hybrid games also provide all the features...
Monadic Second-Order Logic with Arbitrary Monadic Predicates
Nathanaël Fijalkow, Charles Paperman
Article No.: 20
We study Monadic Second-Order Logic (MSO) over finite words, extended with (non-uniform arbitrary) monadic predicates. We show that it defines a class of languages that has algebraic, automata-theoretic, and machine-independent...
On the Parameterized Complexity of Finding Small Unsatisfiable Subsets of CNF Formulas and CSP Instances
Ronald De Haan, Iyad Kanj, Stefan Szeider
Article No.: 21
In many practical settings it is useful to find a small unsatisfiable subset of a given unsatisfiable set of constraints. We study this problem from a parameterized complexity perspective, taking the size of the unsatisfiable subset as the natural...
Horn Fragments of the Halpern-Shoham Interval Temporal Logic
Davide Bresolin, Agi Kurucz, Emilio Muñoz-Velasco, Vladislav Ryzhikov, Guido Sciavicco, Michael Zakharyaschev
Article No.: 22
We investigate the satisfiability problem for Horn fragments of the Halpern-Shoham interval temporal logic depending on the type (box or diamond) of the interval modal operators, the type of the underlying linear order (discrete or dense), and the...
The Complexity of Phylogeny Constraint Satisfaction Problems
Manuel Bodirsky, Peter Jonsson, Trung Van Pham
Article No.: 23
We systematically study the computational complexity of a broad class of computational problems in phylogenetic reconstruction. The class contains, for example, the rooted triple consistency problem, forbidden subtree problems, the quartet...
Continuous Petri nets are a relaxation of classical discrete Petri nets in which transitions can be fired a fractional number of times, and consequently places may contain a fractional number of tokens. Such continuous Petri nets are an appealing...
Collapsible Pushdown Automata and Recursion Schemes
Matthew Hague, Andrzej S. Murawski, C.-H. Luke Ong, Olivier Serre
Article No.: 25
We consider recursion schemes (not assumed to be homogeneously typed, and hence not necessarily safe) and use them as generators of (possibly infinite) ranked trees. A recursion scheme is essentially a finite typed deterministic term...