ACM DL

Computational Logic (TOCL)

Menu

Search Issue
enter search term and/or author name

Archive


ACM Transactions on Computational Logic (TOCL), Volume 18 Issue 3, August 2017

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