<div class="csl-bib-body">
<div class="csl-entry">Labai, N. (2021). <i>Automata-based reasoning for decidable logics with data values</i> [Dissertation, Technische Universität Wien]. reposiTUm. https://doi.org/10.34726/hss.2021.94060</div>
</div>
-
dc.identifier.uri
https://doi.org/10.34726/hss.2021.94060
-
dc.identifier.uri
http://hdl.handle.net/20.500.12708/18567
-
dc.description.abstract
Decidable logics play a major role in knowledge representation, automated verification, and database management. A common ground relating many of these logics is the two-variable fragment of First Order logic (FO2), which is well-suited for handling graph-structured data. Real-world applications nearly always require us to model so-called concrete values such as measurements, strings, and time. As a result, efforts have been made to incorporate data values into DLs, and to extend FO2 with means for modeling data while maintaining decidability.The overarching goal of this thesis is to develop techniques based on automata for reasoning in rich decidable logics that allow to model data values. We concentrate on two different expressive logics with data values, and employ automata for solving the following open problems.First, we consider a DL called ALCP(Zc) that supports constraints given as comparisons of integer numbers. Decidability of this logic has been proven but no upper complexity bounds has been established for the problem. We obtain a tight ExpTime upper bound for deciding concept satisfiability w.r.t. general TBoxes which is, to our knowledge, the first complexity upper bound for reasoning with general TBoxes and discrete concrete domains.Second, we consider the logic FO2 with a linear order, a total preorder, and its induced successor, whose finite satisfiability problem is known to be ExpSpace -complete. We introduce a novel automata model called Pebble-Intervals automata (PIA), study its power in contrast to other automata models, and investigate its emptiness problem and its closure properties. We also obtain an automata-theoretic proof of the upper bound for the finite satisfiability problem of the logic by reducing it to a PIA emptiness test.
en
dc.language
English
-
dc.language.iso
en
-
dc.rights.uri
http://rightsstatements.org/vocab/InC/1.0/
-
dc.subject
Description Logics
en
dc.subject
Decidable Logics
en
dc.subject
Knowledge Representation and Reasoning
en
dc.title
Automata-based reasoning for decidable logics with data values
en
dc.type
Thesis
en
dc.type
Hochschulschrift
de
dc.rights.license
In Copyright
en
dc.rights.license
Urheberrechtsschutz
de
dc.identifier.doi
10.34726/hss.2021.94060
-
dc.contributor.affiliation
TU Wien, Österreich
-
dc.rights.holder
Nadia Labai
-
dc.publisher.place
Wien
-
tuw.version
vor
-
tuw.thesisinformation
Technische Universität Wien
-
tuw.publication.orgunit
E192 - Institut für Logic and Computation
-
dc.type.qualificationlevel
Doctoral
-
dc.identifier.libraryid
AC16333499
-
dc.description.numberOfPages
170
-
dc.thesistype
Dissertation
de
dc.thesistype
Dissertation
en
dc.rights.identifier
In Copyright
en
dc.rights.identifier
Urheberrechtsschutz
de
tuw.advisor.staffStatus
staff
-
tuw.advisor.orcid
0000-0002-2344-9658
-
item.openaccessfulltext
Open Access
-
item.openairecristype
http://purl.org/coar/resource_type/c_db06
-
item.grantfulltext
open
-
item.mimetype
application/pdf
-
item.languageiso639-1
en
-
item.openairetype
doctoral thesis
-
item.fulltext
with Fulltext
-
item.cerifentitytype
Publications
-
crisitem.author.dept
E192-02 - Forschungsbereich Databases and Artificial Intelligence