Artículos con la etiqueta ‘Lógica y ciencia de la computación’

Proceedings of the 8th International Workshop on Non-Monotonic Reasoning, NMR’2000

Por • 20 mar, 2014 • Category: Ambiente

The papers gathered in this collection were presented at the 8th International Workshop on Nonmonotonic Reasoning, NMR2000. The series was started by John McCarthy in 1978. The first international NMR workshop was held at Mohonk Mountain House, New Paltz, New York in June, 1984, and was organized by Ray Reiter and Bonnie Webber. In the last 10 years the area of nonmonotonic reasoning has seen a number of important developments. Significant theoretical advances were made in the understanding of general abstract principles underlying nonmonotonicity. Key results on the expressibility and computational complexity of nonmonotonic logics were established. The role of nonmonotonic reasoning in belief revision, abduction, reasoning about action, planing and uncertainty was further clarified.



A polynomial time complete disjunction property in intuitionistic propositional logic

Por • 16 dic, 2013 • Category: Leyes

We extend the polynomial time algorithms due to Buss and Mints(APAL 1999) and Ferrari, Fiorentini and Fiorino(LPAR 2002) to yield a polynomial time complete disjunction property in intuitionistic propositional logic.



Regular graphs and the spectra of two-variable logic with counting

Por • 14 abr, 2013 • Category: Crítica

The spectrum of a first-order logic sentence is the set of natural numbers that are cardinalities of its finite models. This notion has been shown to be closely linked with complexity theory. In fact, asking whether the spectra of first-order logic sentences is closed under complement is equivalent to asking whether NE=coNE. In this paper we show that when restricted to using only two variables, the spectra of first-order logic sentences are closed under complement. In particular, we show that they are semilinear. At the heart of our proof are semilinear characterisations for the existence of regular graphs, the class of graphs in which there are a priori bounds on the degrees of the vertices.