ACM DL

Computational Logic (TOCL)

Menu

Search Issue
enter search term and/or author name

Archive


ACM Transactions on Computational Logic (TOCL), Volume 8 Issue 4, August 2007

The axiomatic translation principle for modal logic
Renate A. Schmidt, Ullrich Hustadt
Article No.: 19
DOI: 10.1145/1276920.1276921

In this paper we present a translation principle, called the axiomatic translation, for reducing propositional modal logics with background theories, including triangular properties such as transitivity, Euclideanness and functionality, to...

Probabilistic abstraction for model checking: An approach based on property testing
Sophie Laplante, Richard Lassaigne, Frédéric Magniez, Sylvain Peyronnet, Michel de Rougemont
Article No.: 20
DOI: 10.1145/1276920.1276922

The goal of model checking is to verify the correctness of a given program, on all its inputs. The main obstacle, in many cases, is the intractably large size of the program's transition system. Property testing is a randomized method to verify...

First-order queries on structures of bounded degree are computable with constant delay
Arnaud Durand, Etienne Grandjean
Article No.: 21
DOI: 10.1145/1276920.1276923

A relational structure is d-degree-bounded, for some integer d, if each element of the domain belongs to at most d tuples. In this paper, we revisit the complexity of the evaluation problem of not necessarily Boolean...

A sequent calculus and a theorem prover for standard conditional logics
Nicola Olivetti, Gian Luca Pozzato, Camilla B. Schwind
Article No.: 22
DOI: 10.1145/1276920.1276924

In this paper we present a cut-free sequent calculus, called SeqS, for some standard conditional logics. The calculus uses labels and transition formulas and can be used to prove decidability and space complexity bounds for the respective logics....

Removing propagation redundant constraints in redundant modeling
C. W. Choi, J. H.M. Lee, P. J. Stuckey
Article No.: 23
DOI: 10.1145/1276920.1276925

A widely adopted approach to solving constraint satisfaction problems combines systematic tree search with various degrees of constraint propagation for pruning the search space. One common technique to improve the execution efficiency is to add...

Probabilistic interval XML
Edward Hung, Lise Getoor, V. S. Subrahmanian
Article No.: 24
DOI: 10.1145/1276920.1276926

Interest in XML databases has been expanding rapidly over the last few years. In this paper, we study the problem of incorporating probabilistic information into XML databases. We propose the Probabilistic Interval XML (PIXML for...