View in EDS

On the complexity of inconsistency measurement.

Saved in:
Bibliographic Details
Title: On the complexity of inconsistency measurement.
Authors: Thimm, Matthias1 (AUTHOR) thimm@uni-koblenz.de, Wallner, Johannes P.2 (AUTHOR)
Source: Artificial Intelligence. Oct2019, Vol. 275, p411-456. 46p.
Subjects: Computational complexity, Statistical decision making, Measurement
Abstract: We survey a selection of inconsistency measures from the literature and investigate their computational complexity wrt. decision problems related to bounds on the inconsistency value and the functional problem of determining the actual value. Our findings show that those inconsistency measures can be partitioned into four classes related to their complexity. The first three classes contain measures whose complexities are located on the first three levels of the polynomial hierarchy, respectively. The final class is under standard complexity-theoretic assumptions located beyond the polynomial hierarchy. We provide membership results for all the investigated problems and completeness results for most of them. In addition, we undertake a preliminary study on the computational complexity of the measures on fragments of propositional logic. [ABSTRACT FROM AUTHOR]
Copyright of Artificial Intelligence is the property of Elsevier B.V. and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Database: Engineering Source
FullText Text:
  Availability: 0
Header DbId: egs
DbLabel: Engineering Source
An: 138179072
AccessLevel: 6
PubType: Academic Journal
PubTypeId: academicJournal
PreciseRelevancyScore: 0
IllustrationInfo
Items – Name: Title
  Label: Title
  Group: Ti
  Data: On the complexity of inconsistency measurement.
– Name: Author
  Label: Authors
  Group: Au
  Data: <searchLink fieldCode="AR" term="%22Thimm%2C+Matthias%22">Thimm, Matthias</searchLink><relatesTo>1</relatesTo> (AUTHOR)<i> thimm@uni-koblenz.de</i><br /><searchLink fieldCode="AR" term="%22Wallner%2C+Johannes+P%2E%22">Wallner, Johannes P.</searchLink><relatesTo>2</relatesTo> (AUTHOR)
– Name: TitleSource
  Label: Source
  Group: Src
  Data: <searchLink fieldCode="JN" term="%22Artificial+Intelligence%22">Artificial Intelligence</searchLink>. Oct2019, Vol. 275, p411-456. 46p.
– Name: Subject
  Label: Subjects
  Group: Su
  Data: <searchLink fieldCode="DE" term="%22Computational+complexity%22">Computational complexity</searchLink><br /><searchLink fieldCode="DE" term="%22Statistical+decision+making%22">Statistical decision making</searchLink><br /><searchLink fieldCode="DE" term="%22Measurement%22">Measurement</searchLink>
– Name: Abstract
  Label: Abstract
  Group: Ab
  Data: We survey a selection of inconsistency measures from the literature and investigate their computational complexity wrt. decision problems related to bounds on the inconsistency value and the functional problem of determining the actual value. Our findings show that those inconsistency measures can be partitioned into four classes related to their complexity. The first three classes contain measures whose complexities are located on the first three levels of the polynomial hierarchy, respectively. The final class is under standard complexity-theoretic assumptions located beyond the polynomial hierarchy. We provide membership results for all the investigated problems and completeness results for most of them. In addition, we undertake a preliminary study on the computational complexity of the measures on fragments of propositional logic. [ABSTRACT FROM AUTHOR]
– Name: AbstractSuppliedCopyright
  Label:
  Group: Ab
  Data: <i>Copyright of Artificial Intelligence is the property of Elsevier B.V. and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract.</i> (Copyright applies to all Abstracts.)
PLink https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=138179072
RecordInfo BibRecord:
  BibEntity:
    Identifiers:
      – Type: doi
        Value: 10.1016/j.artint.2019.07.001
    Languages:
      – Code: eng
        Text: English
    PhysicalDescription:
      Pagination:
        PageCount: 46
        StartPage: 411
    Subjects:
      – SubjectFull: Computational complexity
        Type: general
      – SubjectFull: Statistical decision making
        Type: general
      – SubjectFull: Measurement
        Type: general
    Titles:
      – TitleFull: On the complexity of inconsistency measurement.
        Type: main
  BibRelationships:
    HasContributorRelationships:
      – PersonEntity:
          Name:
            NameFull: Thimm, Matthias
      – PersonEntity:
          Name:
            NameFull: Wallner, Johannes P.
    IsPartOfRelationships:
      – BibEntity:
          Dates:
            – D: 01
              M: 10
              Text: Oct2019
              Type: published
              Y: 2019
          Identifiers:
            – Type: issn-print
              Value: 00043702
          Numbering:
            – Type: volume
              Value: 275
          Titles:
            – TitleFull: Artificial Intelligence
              Type: main
ResultId 1