The coherence of Lukasiewicz assessments is NP-complete

被引：10

作者：

Bova, Simone ^{[2
]}

Flaminio, Tommaso ^{[1
]}

机构：

[1] Univ Siena, Dept Math & Comp Sci, I-53100 Siena, Italy

[2] Vanderbilt Univ, Dept Math, Stevenson Ctr 1326, Nashville, TN 37240 USA

来源：

INTERNATIONAL JOURNAL OF APPROXIMATE REASONING | 2010年 / 51卷 / 03期

关键词：

De Finetti's coherence criterion; Infinite-valued Lukasiewicz logic; NP-completeness; SMV-algebras; Probabilistic Kripke models; MV-ALGEBRAS; LOGIC; THEOREM; STATES;

D O I：

10.1016/j.ijar.2009.10.002

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

The problem of deciding whether a rational assessment of formulas of infinite-valued Lukasiewicz logic is coherent has been shown to be decidable by Mundici [1] and in PSPACE by Flaminio and Montagna [10]. We settle its computational complexity proving an NP-completeness result. We then obtain NP-completeness results for the satisfiability problem of certain many-valued probabilistic logics introduced by Flaminio and Montagna in [9]. (C) 2009 Elsevier Inc. All rights reserved.

引用

页码：294 / 304

页数：11

共 23 条

[1]

[Anonymous], 1998, Theory of linear and integer programming

[2]

[Anonymous], 1937, Ann. Inst. Henri Poincare

[3]

[Anonymous], THESIS U MILAN

[4]

Chang C.C., 1958, T AM MATH SOC, V88, P467

[5]

Cignoli R., 2013, Algebraic foundations of many-valued reasoning, V7

[6]

De Finetti B., 1974, Theory of Probability, VI

[7]

deFinetti B., 1931, FUND MATH, V17, P298, DOI DOI 10.4064/FM-17-1-298-329

[8]

Edwald G., 1996, COMBINATORIAL CONVEX

[9] Models for Many-Valued Probabilistic Reasoning [J].

Flaminio, Tommaso ;

Montagna, Franco .

JOURNAL OF LOGIC AND COMPUTATION, 2011, 21 (03) :447-464

[10] MV-algebras with internal states and probabilistic fuzzy logics [J].

Flaminio, Tommaso ;

Montagna, Franco .

INTERNATIONAL JOURNAL OF APPROXIMATE REASONING, 2009, 50 (01) :138-152

← 1 2 3 →