Studia Logica (forthcoming)
|Abstract||In the current paper we consider theories with vocabulary containing a number of binary and unary relation symbols. Binary relation symbols represent labeled edges of a graph and unary relations represent unique annotations of the graph’s nodes. Such theories, which we call annotation theories , can be used in many applications, including the formalization of argumentation, approximate reasoning, semantics of logic programs, graph coloring, etc. We address a number of problems related to annotation theories over finite models, including satisfiability, querying problem, specification of preferred models and model checking problem. We show that most of considered problems are NPT ime - or co-NPT ime -complete. In order to reduce the complexity for particular theories, we use second-order quantifier elimination. To our best knowledge none of existing methods works in the case of annotation theories. We then provide a new second-order quantifier elimination method for stratified theories, which is successful in the considered cases. The new result subsumes many other results, including those of [2, 28, 21].|
|Keywords||No keywords specified (fix it)|
|Through your library||Configure|
Similar books and articles
Joseph Berger (2000). Theory and Formalization: Some Reflections on Experience. Sociological Theory 18 (3):482-489.
Ítala M. L. D'Ottaviano (1987). Definability and Quantifier Elimination for J3-Theories. Studia Logica 46 (1):37 - 54.
J. C. E. Dekker (1981). Twilight Graphs. Journal of Symbolic Logic 46 (3):539-571.
George Weaver (1988). Classifying ℵ0-Categorical Theories. Studia Logica 47 (4):327 - 345.
Robert E. Woodrow (1976). A Note on Countable Complete Theories Having Three Isomorphism Types of Countable Models. Journal of Symbolic Logic 41 (3):672-680.
Rolf Backofen, James Rogers & K. Vijay-Shanker (1995). A First-Order Axiomatization of the Theory of Finite Trees. Journal of Logic, Language and Information 4 (1):5-39.
James Loveys & Predrag Tanović (1996). Countable Models of Trivial Theories Which Admit Finite Coding. Journal of Symbolic Logic 61 (4):1279-1286.
M. Krynicki & K. Zdanowski (2005). Theories of Arithmetics in Finite Models. Journal of Symbolic Logic 70 (1):1-28.
Dov M. Gabbay & Andrzej Szałas (2007). Second-Order Quantifier Elimination in Higher-Order Contexts with Applications to the Semantical Analysis of Conditionals. Studia Logica 87 (1):37 - 50.
Ross Willard (1994). Hereditary Undecidability of Some Theories of Finite Structures. Journal of Symbolic Logic 59 (4):1254-1262.
Sorry, there are not enough data points to plot this chart.
Added to index2009-11-21
Total downloads2 ( #232,575 of 549,122 )
Recent downloads (6 months)0
How can I increase my downloads?