Annotation Theories over Finite Graphs

Studia Logica 93 (2/3):147 - 180 (2009)
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 NPTime- or co-NPTime-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 argumentation theory  labeled graphs  annotations  semantics of logic programs  second-order quantifier elimination
Categories (categorize this paper)
DOI 10.2307/40587167
 Save to my reading list
Follow the author(s)
My bibliography
Export citation
Find it on Scholar
Edit this record
Mark as duplicate
Revision history Request removal from index
Download options
PhilPapers Archive

Upload a copy of this paper     Check publisher's policy on self-archival     Papers currently archived: 16,667
External links
Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library
References found in this work BETA
Patrick Blackburn & Jerry Seligman (1995). Hybrid Languages. Journal of Logic, Language and Information 4 (3):251-272.

View all 11 references / Add more references

Citations of this work BETA
Dov M. Gabbay (2009). Fibring Argumentation Frames. Studia Logica 93 (2/3):231 - 295.

Add more citations

Similar books and articles

Monthly downloads

Added to index


Total downloads

6 ( #336,406 of 1,726,249 )

Recent downloads (6 months)

3 ( #231,316 of 1,726,249 )

How can I increase my downloads?

My notes
Sign in to use this feature

Start a new thread
There  are no threads in this forum
Nothing in this forum yet.