Annotation theories over finite graphs
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) | |||||||||
| Categories | ||||||||||
| Options |
|
|||||||||
Download options| PhilPapers Archive |
Upload a copy of this paper Check publisher's policy on self-archival Papers currently archived: 5,701 |
| External links |
 |
| Through your library | Configure |
Similar books and articlesJoseph 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.
Analytics
Monthly downloads
Sorry, there are not enough data points to plot this chart.
|
Added to index2009-11-21Total downloads2 ( #232,575 of 549,122 )Recent downloads (6 months)0How can I increase my downloads? |
My notes
Discussion
