Ghent University Academic Bibliography

Advanced

Satisfiability checking in Łukasiewicz logic as finite constraint satisfaction

Steven Schockaert UGent, Jeroen Janssen UGent and Dirk Vermeir (2012) JOURNAL OF AUTOMATED REASONING. 49(4). p.493-550
abstract
Although it is well-known that every satisfiable formula in Aukasiewicz' infinite-valued logic can be satisfied in some finite-valued logic, practical methods for finding an appropriate number of truth degrees do currently not exist. Extending upon earlier results by Aguzzoli et al., which only take the total number of variable occurrences into account, we present a detailed analysis of what type of formulas require a large number of truth degrees to be satisfied. In particular, we reveal important links between this number of truth degrees and the dimension, and structure, of the cycle space of an associated bipartite graph. We furthermore propose an efficient, polynomial-time algorithm for establishing a strong upper bound on the required number of truth degrees, allowing us to check the satisfiability of sets of formulas in , and more generally, sets of fuzzy clauses over Aukasiewicz logic formulas, by solving a small number of constraint satisfaction problems. In an experimental evaluation, we demonstrate the practical usefulness of this approach, comparing it with a state-of-the-art technique based on mixed integer programming.
Please use this url to cite or link to this publication:
author
organization
alternative title
Satisfiability checking in Lukasiewicz logic as finite constraint satisfaction
year
type
journalArticle (original)
publication status
published
subject
keyword
Satisfiability checking, Fuzzy logic, Lukasiewicz semantics, FUZZY LOGIC, PROPOSITIONAL CALCULI, LUKASIEWICZ LOGIC, VALUED LOGICS, SAT, ALGORITHM
journal title
JOURNAL OF AUTOMATED REASONING
J. Autom. Reasoning
volume
49
issue
4
pages
493 - 550
Web of Science type
Article
Web of Science id
000310431200001
JCR category
COMPUTER SCIENCE, ARTIFICIAL INTELLIGENCE
JCR impact factor
0.567 (2012)
JCR rank
92/114 (2012)
JCR quartile
4 (2012)
ISSN
0168-7433
DOI
10.1007/s10817-011-9227-0
language
English
UGent publication?
yes
classification
A1
copyright statement
I have transferred the copyright for this publication to the publisher
id
1938051
handle
http://hdl.handle.net/1854/LU-1938051
date created
2011-10-28 17:56:07
date last changed
2013-07-15 11:41:08
@article{1938051,
  abstract     = {Although it is well-known that every satisfiable formula in Aukasiewicz' infinite-valued logic can be satisfied in some finite-valued logic, practical methods for finding an appropriate number of truth degrees do currently not exist. Extending upon earlier results by Aguzzoli et al., which only take the total number of variable occurrences into account, we present a detailed analysis of what type of formulas require a large number of truth degrees to be satisfied. In particular, we reveal important links between this number of truth degrees and the dimension, and structure, of the cycle space of an associated bipartite graph. We furthermore propose an efficient, polynomial-time algorithm for establishing a strong upper bound on the required number of truth degrees, allowing us to check the satisfiability of sets of formulas in , and more generally, sets of fuzzy clauses over Aukasiewicz logic formulas, by solving a small number of constraint satisfaction problems. In an experimental evaluation, we demonstrate the practical usefulness of this approach, comparing it with a state-of-the-art technique based on mixed integer programming.},
  author       = {Schockaert, Steven and Janssen, Jeroen and Vermeir, Dirk},
  issn         = {0168-7433},
  journal      = {JOURNAL OF AUTOMATED REASONING},
  keyword      = {Satisfiability checking,Fuzzy logic,Lukasiewicz semantics,FUZZY LOGIC,PROPOSITIONAL CALCULI,LUKASIEWICZ LOGIC,VALUED LOGICS,SAT,ALGORITHM},
  language     = {eng},
  number       = {4},
  pages        = {493--550},
  title        = {Satisfiability checking in \unmatched{0141}ukasiewicz logic as finite constraint satisfaction},
  url          = {http://dx.doi.org/10.1007/s10817-011-9227-0},
  volume       = {49},
  year         = {2012},
}

Chicago
Schockaert, Steven, Jeroen Janssen, and Dirk Vermeir. 2012. “Satisfiability Checking in Łukasiewicz Logic as Finite Constraint Satisfaction.” Journal of Automated Reasoning 49 (4): 493–550.
APA
Schockaert, S., Janssen, J., & Vermeir, D. (2012). Satisfiability checking in Łukasiewicz logic as finite constraint satisfaction. JOURNAL OF AUTOMATED REASONING, 49(4), 493–550.
Vancouver
1.
Schockaert S, Janssen J, Vermeir D. Satisfiability checking in Łukasiewicz logic as finite constraint satisfaction. JOURNAL OF AUTOMATED REASONING. 2012;49(4):493–550.
MLA
Schockaert, Steven, Jeroen Janssen, and Dirk Vermeir. “Satisfiability Checking in Łukasiewicz Logic as Finite Constraint Satisfaction.” JOURNAL OF AUTOMATED REASONING 49.4 (2012): 493–550. Print.