ACM DL

Computational Logic (TOCL)

Menu

Search Issue
enter search term and/or author name

Archive


ACM Transactions on Computational Logic (TOCL), Volume 12 Issue 4, July 2011

A system of interaction and structure IV: The exponentials and decomposition
Lutz Straß Burger, Alessio Guglielmi
Article No.: 23
DOI: 10.1145/1970398.1970399

We study a system, called NEL, which is the mixed commutative/noncommutative linear logic BV augmented with linear logic's exponentials. Equivalently, NEL is MELL augmented with the noncommutative self-dual connective seq. In this article, we show...

Complexity of conservative constraint satisfaction problems
Andrei A. Bulatov
Article No.: 24
DOI: 10.1145/1970398.1970400

In a constraint satisfaction problem (CSP), the aim is to find an assignment of values to a given set of variables, subject to specified constraints. The CSP is known to be NP-complete in general. However, certain restrictions on the form of the...

Logic programs with propositional connectives and aggregates
Paolo Ferraris
Article No.: 25
DOI: 10.1145/1970398.1970401

Answer set programming (ASP) is a logic programming paradigm that can be used to solve complex combinatorial search problems. Aggregates are an ASP construct that plays an important role in many applications. Defining a satisfactory semantics of...

Unification and matching on compressed terms
Adrià Gascón, Guillem Godoy, Manfred Schmidt-Schauss
Article No.: 26
DOI: 10.1145/1970398.1970402

Term unification plays an important role in many areas of computer science, especially in those related to logic. The universal mechanism of grammar-based compression for terms, in particular the so-called singleton tree grammars (STGAs),...

Two-variable logic on data words
Mikołaj Bojańczyk, Claire David, Anca Muscholl, Thomas Schwentick, Luc Segoufin
Article No.: 27
DOI: 10.1145/1970398.1970403

In a data word each position carries a label from a finite alphabet and a data value from some infinite domain. This model has been already considered in the realm of semistructured data, timed automata, and extended temporal logics.

...

Qualitative concurrent parity games
Krishnendu Chatterjee, Luca De Alfaro, Thomas A. Henzinger
Article No.: 28
DOI: 10.1145/1970398.1970404

We consider two-player games played on a finite state space for an infinite number of rounds. The games are concurrent: in each round, the two players (player 1 and player 2) choose their moves independently and simultaneously; the current...

Logics for information systems and their dynamic extensions
Md. Aquil Khan, Mohua Banerjee
Article No.: 29
DOI: 10.1145/1970398.1970405

The article proposes logics for information systems, which provide information about a set of objects regarding a set of attributes. Both “complete” and “incomplete” information systems are dealt with....