liu.seSearch for publications in DiVA
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Annotation Theories over Finite Graphs
Warsaw University.
Linköping University, Department of Computer and Information Science, KPLAB - Knowledge Processing Lab. Linköping University, The Institute of Technology.
2009 (English)In: Studia Logica: An International Journal for Symbolic Logic, ISSN 0039-3215, E-ISSN 1572-8730, Vol. 93, no 2-3, p. 147-180Article in journal (Refereed) Published
Abstract [en]

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].

Place, publisher, year, edition, pages
Springer , 2009. Vol. 93, no 2-3, p. 147-180
Keywords [en]
argumentation theory - labeled graphs - annotations - semantics of logic programs - second-order quantifier elimination
National Category
Engineering and Technology
Identifiers
URN: urn:nbn:se:liu:diva-65966DOI: 10.1007/s11225-009-9220-3OAI: oai:DiVA.org:liu-65966DiVA, id: diva2:400675
Available from: 2011-02-28 Created: 2011-02-28 Last updated: 2017-12-11

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full text

Authority records

Szalas, Andrzej

Search in DiVA

By author/editor
Szalas, Andrzej
By organisation
KPLAB - Knowledge Processing LabThe Institute of Technology
In the same journal
Studia Logica: An International Journal for Symbolic Logic
Engineering and Technology

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 147 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf