Search ACM DL

Search Issue

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

DOI: 10.1145/3091527

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...

**Differential Hybrid Games**

André Platzer

Article No.: 19

DOI: 10.1145/3091123

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

DOI: 10.1145/3091124

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

DOI: 10.1145/3091528

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

DOI: 10.1145/3105909

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

DOI: 10.1145/3105907

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...

**The Logical View on Continuous Petri Nets**

Michael Blondin, Alain Finkel, Christoph Haase, Serge Haddad

Article No.: 24

DOI: 10.1145/3105908

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

DOI: 10.1145/3091122

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...