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
  • 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
Circuit Satisfiability and Constraint Satisfaction Around Skolem Arithmetic
University of Wurzburg, Germany.
Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, Faculty of Science & Engineering.
Middlesex University, England.
2016 (English)In: Pursuit of the Universal, SPRINGER INT PUBLISHING AG , 2016, Vol. 9709, 323-332 p.Conference paper, Published paper (Refereed)
Abstract [en]

We study interactions between Skolem Arithmetic and certain classes of Circuit Satisfiability and Constraint Satisfaction Problems (CSPs). We revisit results of Gla beta er et al. [16] in the context of CSPs and settle the major open question from that paper, finding a certain satisfiability problem on circuits-involving complement, intersection, union and multiplication-to be decidable. This we prove using the decidability of Skolem Arithmetic. Then we solve a second question left open in [16] by proving a tight upper bound for the similar circuit satisfiability problem involving just intersection, union and multiplication. We continue by studying first-order expansions of Skolem Arithmetic without constants, (N; x), as CSPs. We find already here a rich landscape of problems with non-trivial instances that are in P as well as those that are NP-complete.

Place, publisher, year, edition, pages
SPRINGER INT PUBLISHING AG , 2016. Vol. 9709, 323-332 p.
Series
Lecture Notes in Computer Science, ISSN 0302-9743
National Category
Mathematical Analysis
Identifiers
URN: urn:nbn:se:liu:diva-133553DOI: 10.1007/978-3-319-40189-8_33ISI: 000389414700033ISBN: 978-3-319-40189-8; 978-3-319-40188-1 (print)OAI: oai:DiVA.org:liu-133553DiVA: diva2:1060837
Conference
12th Conference on Computability in Europe (CiE)
Available from: 2016-12-30 Created: 2016-12-29 Last updated: 2016-12-30

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Jonsson, Peter
By organisation
Software and SystemsFaculty of Science & Engineering
Mathematical Analysis

Search outside of DiVA

GoogleGoogle Scholar

Altmetric score

Total: 9 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • 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