Results 1 to 10 of about 2,832 (68)

Infinite and Bi-infinite Words with Decidable Monadic Theories [PDF]

, 2018
We study word structures of the form $(D,
Kuske, Dietrich, Liu, Jiamou, Moskvina, Anastasia   +2 more
core   +2 more sources

Progression and Verification of Situation Calculus Agents with Bounded Beliefs [PDF]

, 2016
We investigate agents that have incomplete information and make decisions based on their beliefs expressed as situation calculus bounded action theories.
DE GIACOMO, Giuseppe, Lesperance, Y., PATRIZI, FABIO, VASSOS, STAVROS   +3 more
core   +1 more source

Monadic second order finite satisfiability and unbounded tree-width [PDF]

, 2016
The finite satisfiability problem of monadic second order logic is decidable only on classes of structures of bounded tree-width by the classic result of Seese (1991). We prove the following problem is decidable: Input: (i) A monadic second order logic
Kotek, Tomer, Veith, Helmut, Zuleger, Florian   +2 more
core   +2 more sources

Godel's Incompleteness Phenomenon - Computationally [PDF]

, 2014
We argue that Godel's completeness theorem is equivalent to completability of consistent theories, and Godel's incompleteness theorem is equivalent to the fact that this completion is not constructive, in the sense that there are some consistent and ...
Salehi, Saeed
core   +3 more sources

Querying the Guarded Fragment [PDF]

, 2014
Evaluating a Boolean conjunctive query Q against a guarded first-order theory F is equivalent to checking whether "F and not Q" is unsatisfiable. This problem is relevant to the areas of database theory and description logic.
Bárány, Vince, Gottlob, Georg, Otto, Martin   +2 more
core   +2 more sources

Logics for Unranked Trees: An Overview [PDF]

, 2005
Labeled unranked trees are used as a model of XML documents, and logical languages for them have been studied actively over the past several years. Such logics have different purposes: some are better suited for extracting data, some for expressing ...
A. Arnold, B. Courcelle, B. Courcelle, B.-H. Schlingloff, E. Clarke, F. Moller, F. Neven, F. Neven, G. Gottlob, G. Gottlob, I. Walukiewicz, J. Niehren, J.R. Büchi, J.W. Thatcher, J.W. Thatcher, L. Cardelli, L. Cardelli, L. Libkin, L. Stockmeyer, M. Benedikt, M. Grohe, M. Rabin, M.Y. Vardi, P. Bouyer, S. Abiteboul, T. Hafer, W. Thomas   +26 more
core   +6 more sources

Verifying the Interplay of Authorization Policies and Workflow in Service-Oriented Architectures (Full version)

, 2009
A widespread design approach in distributed applications based on the service-oriented paradigm, such as web-services, consists of clearly separating the enforcement of authorization policies and the workflow of the applications, so that the interplay ...
Barletta, Michele, Ranise, Silvio, Viganò, Luca   +2 more
core   +2 more sources

Modal Logics of Topological Relations [PDF]

, 2006
Logical formalisms for reasoning about relations between spatial regions play a fundamental role in geographical information systems, spatial and constraint databases, and spatial reasoning in AI.
A. Artale and E. Franconi, A. G. Cohn and S. Hazarika, B. Bennett, B. Bennett, B. Clarke, B. Nebel and H. Bürckert, C. Lutz, C.H. Papadimitriou, D. Suciu, and V. Via, Carsten Lutz, D. Harel, F. Wolter, Frank Wolter, G. Gargov and V.Goranko, I. Düntsch, H. Wang, and S. McCloskey, I. Pratt and D. Schoop, I. Pratt-Hartmann, I. Shapirovsky and V. Shehtman, J. Burgess, J. F. Allen, J. G. Stell, J. Mc Kinsey and A. Tarski, J. Renz, J. Renz and B. Nebel, J.Y. Halpern and Y. Shoham, K. Etessami, M. Y. Vardi, and T. Wilke, M. de Rijke, M. Egenhofer, M. Egenhofer and R. Franzosa, M. Marx and M. Reynolds, M. Reynolds and M. Zakharyaschev, R. Maddux, V. Goranko and D. Vakarelov, V. Goranko and S. Passy, Y. Venema, Yde Venema   +34 more
core   +2 more sources

How unprovable is Rabin's decidability theorem?

, 2015
We study the strength of set-theoretic axioms needed to prove Rabin's theorem on the decidability of the MSO theory of the infinite binary tree. We first show that the complementation theorem for tree automata, which forms the technical core of typical ...
Beckmann A., Davis M., Friedman H., Klarlund N., MedSalem M. O., Pohlers W., Rabin M. O.   +6 more
core   +1 more source

Undecidable First-Order Theories of Affine Geometries [PDF]

, 2012
Tarski initiated a logic-based approach to formal geometry that studies first-order structures with a ternary betweenness relation (\beta) and a quaternary equidistance relation (\equiv).
Kuusisto, Antti, Meyers, Jeremy, Virtema, Jonni   +2 more
core   +7 more sources