ACM DL

Computational Logic (TOCL)

Menu

Search Issue
enter search term and/or author name

Archive


ACM Transactions on Computational Logic (TOCL), Volume 9 Issue 2, March 2008

A comprehensive combination framework
Silvio Ghilardi, Enrica Nicolini, Daniele Zucchelli
Article No.: 8
DOI: 10.1145/1342991.1342992

We define a general notion of a fragment within higher-order type theory; a procedure for constraint satisfiability in combined fragments is outlined, following Nelson-Oppen schema. The procedure is in general only sound, but it becomes...

Coordination in answer set programming
Chiaki Sakama, Katsumi Inoue
Article No.: 9
DOI: 10.1145/1342991.1342993

This article studies a semantics of multiple logic programs, and synthesizes a program having such a collective semantics. More precisely, the following two problems are considered: given two logic programs P1 and...

Alternating timed automata
Slawomir Lasota, Igor Walukiewicz
Article No.: 10
DOI: 10.1145/1342991.1342994

A notion of alternating timed automata is proposed. It is shown that such automata with only one clock have decidable emptiness problem over finite words. This gives a new class of timed languages that is closed under boolean operations and which...

Bounds on the automata size for Presburger arithmetic
Felix Klaedtke
Article No.: 11
DOI: 10.1145/1342991.1342995

Automata provide a decision procedure for Presburger arithmetic. However, until now only crude lower and upper bounds were known on the sizes of the automata produced by the automata-based approach for Presburger arithmetic. In this article, we...

Durations and parametric model-checking in timed automata
Véronique Bruyère, Emmanuel Dall'olio, Jean-François Raskin
Article No.: 12
DOI: 10.1145/1342991.1342996

We consider the problem of model-checking a parametric extension of the logic TCTL over timed automata and establish its decidability. Given a timed automaton, we show that the set of durations of runs starting from a region and ending in another...

First-order complete and computationally complete query languages for spatio-temporal databases
Floris Geerts, Sofie Haesevoets, Bart Kuijpers
Article No.: 13
DOI: 10.1145/1342991.1342997

We address a fundamental question concerning spatio-temporal database systems: “What are exactly spatio-temporal queries?” We define spatio-temporal queries to be computable mappings that are also generic, meaning that the...

A logic of nonmonotone inductive definitions
Marc Denecker, Eugenia Ternovska
Article No.: 14
DOI: 10.1145/1342991.1342998

Well-known principles of induction include monotone induction and different sorts of nonmonotone induction such as inflationary induction, induction over well-founded sets and iterated induction. In this work, we define a logic formalizing...