Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
ATZ-Fachkongress

Chassis.tech plus 2024


4 Kongresse in einer Veranstaltung

Treffen Sie in München die Fachleute von Chassis, Lenkung, Bremsen sowie Reifen/Räder.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
A Tour of Franz Baader’s Contributions to Knowledge Representation and Automated Deduction Kapitel lesen Erstes Kapitel lesen

2019 | OriginalPaper | Buchkapitel

Presburger Concept Cardinality Constraints in Very Expressive Description Logics

Allegro sexagenarioso ma non ritardando

verfasst von : “Johann” Sebastian Rudolph

Erschienen in: Description Logic, Theory Combination, and All That

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

Quantitative information plays an increasingly important role in knowledge representation. To this end, many formalisms have been proposed that enrich traditional KR formalisms by counting and some sort of arithmetics. Baader and Ecke (2017) propose an extension of the description logic \(\mathcal {ALC}\) by axioms which express correspondences between the cardinalities of concepts by means of Presburger arithmetics. This paper extends their results, enhancing the expressivity of the underlying logic as well as the constraints while preserving complexities. It also widens the scope of investigation from finite models to the classical semantics where infinite models are allowed. We also provide first results on query entailment in such logics. As opposed to prior work, our results are established by polynomially encoding the cardinality constraints in the underlying logic.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren
Vorheriges Kapitel Building and Combining Matching Algorithms
Nächstes Kapitel A Note on Unification, Subsumption and Unification Type
Fußnoten
1
I hereby sincerely apologize to Anni, Carsten, Cesare, Frank, and Uli for pushing the submission deadline.
 
2
The original definition of \(\mathcal {SROIQ}\) Rboxes also features explicit axioms expressing role reflexivity, asymmetry, and role disjointness. However, in the presence of (safe) Boolean role constructors, these can be expressed, so we omit them here.
 
3
For this, we have to postulate \(\infty < \infty \), which is debatable, but could be justified by the fact that there is an injective, non-surjective mapping between any two countably infinite sets.
 
4
In fact, the constraint expression \((1+|\mathtt {A}|=|\mathtt {A}|)\wedge \lnot (|\mathtt {A}|=|\mathtt {B}|)\) would enforce finiteness of the extension of \(\mathtt {B}\), which is not axiomatizable in first order logic, neither finitely nor infinitely. For good reasons (see Section 5) we define ECboxes in a way that a first-order axiomatization is still possible.
 
Literatur
1.
2.
Baader, F.: Expressive cardinality constraints on \(\cal{ALCSCC}\) concepts. In: Proceedings of the 34th ACM/SIGAPP Symposium on Applied Computing (SAC 2019). ACM (2019)
3.
Baader, F., Bednarczyk, B., Rudolph, S.: Satisfiability checking and conjunctive query answering in description logics with global and local cardinality constraints. In: Proceedings of the 32nd International Workshop on Description Logics (DL 2019). CEUR Workshop Proceedings. CEUR-WS.org (2019, submitted)
4.
Baader, F., Calvanese, D., McGuinness, D., Nardi, D., Patel-Schneider, P. (eds.): The Description Logic Handbook: Theory, Implementation, and Applications, 2nd edn. Cambridge University Press, Cambridge (2007)MATH
5.
Baader, F., Ecke, A.: Extending the description logic \(\cal{ALC}\) with more expressive cardinality constraints on concepts. In: 3rd Global Conference on Artificial Intelligence (GCAI 2017). EPiC Series in Computing, vol. 50, pp. 6–19. EasyChair (2017)
6.
Baader, F., Horrocks, I., Lutz, C., Sattler, U.: An Introduction to Description Logic. Cambridge University Press, Cambridge (2017)CrossRef
7.
Bach, J.S.: Canon circularis per tonos. In: The Musical Offering, BWV, vol. 1079. Leipzig (1747)
8.
Bednarczyk, B., Rudolph, S.: Worst-case optimal querying of very expressive description logics with path expressions and succinct counting. In: Proceedings of the 32nd International Workshop on Description Logics (DL 2019). CEUR Workshop Proceedings, CEUR-WS.org (2019, submitted)
9.
Cantor, G.: Beiträge zur Begründung der transfiniten Mengenlehre. Math. Ann. 46(4), 481–512 (1895)CrossRef
10.
11.
Demri, S., Nivelle, H.: Deciding regular grammar logics with converse through first-order logic. J. Logic Lang. Inf. 14(3), 289–329 (2005)MathSciNetCrossRef
12.
Demri, S., Lugiez, D.: Complexity of modal logics with Presburger constraints. J. Appl. Logic 8(3), 233–252 (2010)MathSciNetCrossRef
13.
Glimm, B., Horrocks, I., Motik, B., Stoilos, G., Wang, Z.: HermiT: an OWL 2 reasoner. J. Autom. Reason. 53(3), 245–269 (2014)CrossRef
14.
Glimm, B., Kazakov, Y., Lutz, C.: Status QIO: an update. In: Rosati, R., Rudolph, S., Zakharyaschev, M. (eds.) Proceedings of the 24th International Workshop on Description Logics (DL 2011). CEUR Workshop Proceedings, vol. 745. CEUR-WS.org (2011)
15.
16.
Horrocks, I., Kutz, O., Sattler, U.: The even more irresistible \(\cal{SROIQ}\). In: Doherty, P., Mylopoulos, J., Welty, C.A. (eds.) Proceedings of the 10th International Conference on Principles of Knowledge Representation and Reasoning (KR 2006), pp. 57–67. AAAI Press (2006)
17.
Kazakov, Y.: \(\cal{RIQ}\) and \(\cal{SROIQ}\) are harder than \(\cal{SHOIQ}\). In: Brewka, G., Lang, J. (eds.) Proceedings of the 11th International Conference on Principles of Knowledge Representation and Reasoning (KR 2008), pp. 274–284. AAAI Press (2008)
18.
Krötzsch, M., Rudolph, S.: Nominal schemas in description logics: complexities clarified. In: Baral, C., De Giacomo, G., Eiter, T. (eds.) Proceedings of the 14th International Conference on Principles of Knowledge Representation and Reasoning (KR 2014), pp. 308–317. AAAI Press (2014)
19.
20.
Lutz, C., Sattler, U., Tendera, L.: The complexity of finite model reasoning in description logics. Inf. Comput. 199(1–2), 132–171 (2005)MathSciNetCrossRef
21.
22.
Pratt-Hartmann, I.: Complexity of the two-variable fragment with counting quantifiers. J. Logic Lang. Inf. 14, 369–395 (2005)MathSciNetCrossRef
23.
Pratt-Hartmann, I.: Complexity of the guarded two-variable fragment with counting quantifiers. J. Log. Comput. 17(1), 133–155 (2007)MathSciNetCrossRef
24.
Pratt-Hartmann, I.: Data-complexity of the two-variable fragment with counting quantifiers. Inf. Comput. 207(8), 867–888 (2009)MathSciNetCrossRef
25.
Pratt-Hartmann, I.: Personal communication, 19 March 2019
26.
27.
Rudolph, S., Glimm, B.: Nominals, inverses, counting, and conjunctive queries or: why infinity is your friend! J. Artif. Intell. Res. 39, 429–481 (2010)MathSciNetCrossRef
28.
Rudolph, S., Krötzsch, M.: Flag & check: data access with monadically defined queries. In: Hull, R., Fan, W. (eds.) Proceedings of the 32nd Symposium on Principles of Database Systems (PODS 2013), pp. 151–162. ACM (2013)
29.
30.
Sirin, E., Parsia, B., Grau, B.C., Kalyanpur, A., Katz, Y.: Pellet: a practical OWL-DL reasoner. J. Web Seman. 5(2), 51–53 (2007)CrossRef
31.
Skolem, T.: Über einige Grundlagenfragen der Mathematik. Skrifter utgitt av det Norske Videnskaps-Akademi i Oslo, I. Matematisk-naturvidenskabelig Klasse 7, 1–49 (1929)
32.
Steigmiller, A., Liebig, T., Glimm, B.: Konclude: system description. J. Web Seman. 27, 78–85 (2014)CrossRef
33.
Tobies, S.: Complexity results and practical algorithms for logics in knowledge representation. Ph.D. thesis, RWTH Aachen, Germany (2001)
Metadaten
Titel
Presburger Concept Cardinality Constraints in Very Expressive Description Logics
verfasst von
“Johann” Sebastian Rudolph
Copyright-Jahr
2019
Buch
Description Logic, Theory Combination, and All That

Print ISBN: 978-3-030-22101-0

Electronic ISBN: 978-3-030-22102-7

Copyright-Jahr: 2019

DOI
https://doi.org/10.1007/978-3-030-22102-7_25

Premium Partner

    Bildnachweise