ACM DL

Computational Logic (TOCL)

Menu

Search Issue
enter search term and/or author name

Archive


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

Epistemic Strategies and Games on Concurrent Processes
Konstantinos Chatzikokolakis, Sophia Knight, Catuscia Palamidessi, Prakash Panangaden
Article No.: 28
DOI: 10.1145/2362355.2362356

We develop a game semantics for process algebra with two interacting agents. The purpose of our semantics is to make manifest the role of knowledge and information flow in the interactions between agents and to control the information available to...

Translating to Co-Büchi Made Tight, Unified, and Useful
Udi Boker, Orna Kupferman
Article No.: 29
DOI: 10.1145/2362355.2362357

We solve the longstanding open problems of the blow-up involved in the translations, when possible, of a nondeterministic Büchi word automaton (NBW) to a nondeterministic co-Büchi word automaton (NCW) and to a deterministic co-Büchi...

Maps in Multiple Belief Change
Pavlos Peppas, Costas D. Koutras, Mary-Anne Williams
Article No.: 30
DOI: 10.1145/2362355.2362358

Multiple Belief Change extends the classical AGM framework for Belief Revision introduced by Alchourron, Gardenfors, and Makinson in the early ’80s. The extended framework includes epistemic input represented as a (possibly infinite) set...

Hierarchies in Dependence Logic
Arnaud Durand, Juha Kontinen
Article No.: 31
DOI: 10.1145/2362355.2362359

We study fragments D(k∀) and D(k-dep) of dependence logic defined either by restricting the number k of universal quantifiers or the width of dependence atoms in formulas. We find the sublogics of...

A Generalized QSQR Evaluation Method for Horn Knowledge Bases
Ewa Madalińska-Bugaj, Linh Anh Nguyen
Article No.: 32
DOI: 10.1145/2362355.2362360

We generalize the QSQR evaluation method to give the first set-oriented depth-first evaluation method for Horn knowledge bases. The resulting procedure closely simulates SLD-resolution (to take advantages of the goal-directed approach) and highly...

Fuzzy Equilibrium Logic: Declarative Problem Solving in Continuous Domains
Steven Schockaert, Jeroen Janssen, Dirk Vermeir
Article No.: 33
DOI: 10.1145/2362355.2362361

In this article, we introduce fuzzy equilibrium logic as a generalization of both Pearce equilibrium logic and fuzzy answer set programming. The resulting framework combines the capability of equilibrium logic to declaratively specify search...

Decidability of Downward XPath
Diego Figueira
Article No.: 34
DOI: 10.1145/2362355.2362362

We investigate the satisfiability problem for downward-XPath, the fragment of XPath that includes the child and descendant axes, and tests for (in)equality of attributes’ values. We prove that this problem is decidable, EXPTIME-complete....