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
A Paraconsistent ASP-like Language with Tractable Model Generation
Linköping University, Department of Computer and Information Science, Artificial Intelligence and Integrated Computer Systems. Linköping University, Faculty of Science & Engineering. University of Warsaw, Warsaw, Poland.ORCID iD: 0000-0002-6000-6581
2020 (English)In: Journal of Applied Logics - IfCoLog Journal of Logic and Applications, ISSN 2631-9810, Vol. 7, no 3, p. 361-389Article in journal (Refereed) Published
Abstract [en]

Answer Set Programming (ASP) is nowadays a dominant rule-based knowledge representation tool. Though existing ASP variants enjoy efficient implementations, generating an answer set remains intractable. The goal of this research is to define a new ASP-like rule language, 4SP, with tractable model generation. The language combines ideas of ASP and a paraconsistent rule language 4QL. Though 4SP shares the syntax of ASP and for each program all its answer sets are among 4SP models, the new language differs from ASP in its logical foundations, the intended methodology of its use and complexity of computing models. As we show in the paper, 4QL can be seen as a paraconsistent counterpart of ASP programs stratified with respect to default negation. Although model generation for 4QL programs is tractable, dropping stratification makes it intractable for both 4QL and ASP. To retain tractability while allowing non-stratified programs, in 4SP we introduce trial expressions interlacing programs with hypotheses as to the truth values of default negations. This allows us to develop a model generation algorithm with deterministic polynomial time complexity. We also show relationships among 4SP, ASP and 4QL.

Place, publisher, year, edition, pages
London: College Publications, 2020. Vol. 7, no 3, p. 361-389
National Category
Computer and Information Sciences
Identifiers
URN: urn:nbn:se:liu:diva-169094OAI: oai:DiVA.org:liu-169094DiVA, id: diva2:1465035
Note

Funding agencies: This work has been supported by grant 2017/27/B/ST6/02018 of the National Science Centre Poland.

Available from: 2020-09-08 Created: 2020-09-08 Last updated: 2020-10-19Bibliographically approved

Open Access in DiVA

fulltext(1830 kB)236 downloads
File information
File name FULLTEXT01.pdfFile size 1830 kBChecksum SHA-512
a4d91c05cc8a16a97e8aa683979908032303748ddd8cbeee370c0448a2aed8cc96b8e114bd89328f49be3240f685f3c5f0d7563893ee69ca90fbe05e76e8c57c
Type fulltextMimetype application/pdf

Other links

Link to article

Authority records

Szalas, Andrzej

Search in DiVA

By author/editor
Szalas, Andrzej
By organisation
Artificial Intelligence and Integrated Computer SystemsFaculty of Science & Engineering
Computer and Information Sciences

Search outside of DiVA

GoogleGoogle Scholar
Total: 236 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

urn-nbn

Altmetric score

urn-nbn
Total: 338 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