ACM DL

Computational Logic (TOCL)

Menu

Search Issue
enter search term and/or author name

Archive


ACM Transactions on Computational Logic (TOCL), Volume 4 Issue 4, October 2003

A dynamic approach to characterizing termination of general logic programs
Yi-Dong Shen, Jia-Huai You, Li-Yan Yuan, Samuel S. P. Shen, Qiang Yang
Pages: 417-430
DOI: 10.1145/937555.937556
We present a new characterization of termination of general logic programs. Most existing termination analysis approaches rely on some static information about the structure of the source code of a logic program, such as modes/types, norms/level...

Variable independence for first-order definable constraints
Leonid Libkin
Pages: 431-451
DOI: 10.1145/937555.937557
Whenever we have data represented by constraints (such as order, linear, polynomial, etc.), running time for many constraint processing algorithms can be considerably lowered if it is known that certain variables in those constraints are independent...

Model checking stochastic automata
Jeremy Bryans, Howard Bowman, John Derrick
Pages: 452-492
DOI: 10.1145/937555.937558
Modern distributed systems include a class of applications in which non-functional requirements are important. In particular, these applications include multimedia facilities where real time constraints are crucial to their correct functioning. In...

Higher-order pattern complement and the strict λ-calculus
Alberto Momigliano, Frank Pfenning
Pages: 493-529
DOI: 10.1145/937555.937559
We address the problem of complementing higher-order patterns without repetitions of existential variables. Differently from the first-order case, the complement of a pattern cannot, in general, be described by a pattern, or even by a finite set of...

Interaction between path and type constraints
Peter Buneman, Wenfei Fan, Scott Weinstein
Pages: 530-577
DOI: 10.1145/937555.937560
Path constraints are capable of expressing inclusion and inverse relationships and have proved useful in modeling and querying semistructured data [Abiteboul and Vianu 1999; Buneman et al. 2000]. Types also constrain the structure of data and are...

Abstract state machines capture parallel algorithms
Andreas Blass, Yuri Gurevich
Pages: 578-651
DOI: 10.1145/937555.937561
We give an axiomatic description of parallel, synchronous algorithms. Our main result is that every such algorithm can be simulated, step for step, by an abstract state machine with a background that provides for multisets....