Top

Published in:

2018 | OriginalPaper | Chapter

Deciding Open Definability via Subisomorphisms

Authors : Carlos Areces, Miguel Campercholi, Pablo Ventura

Published in: Logic, Language, Information, and Computation

Publisher: Springer Berlin Heidelberg

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Given a logic \(\varvec{\mathcal {L}}\), the \(\varvec{\mathcal {L}}\)-Definability Problem for finite structures takes as input a finite structure \(\varvec{A}\) and a target relation T over the domain of \(\varvec{A}\), and determines whether there is a formula of \(\varvec{\mathcal {L}}\) whose interpretation in \(\varvec{A}\) coincides with T. In this note we present an algorithm that solves the definability problem for quantifier-free first order formulas. Our algorithm takes advantage of a semantic characterization of open definability via subisomorphisms, which is sound and complete. We also provide an empirical evaluation of its performance.

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now

previous chapter A Formalization of Brouwer’s Argument for Bar Induction

next chapter APAL with Memory Is Better

Available only for authorised users

Clarke, E., Grumberg, O., Peled, D.: Model Checking. MIT Press, Cambridge (1999)

Berard, B., Bidoit, M., Finkel, A., Laroussinie, F., Petit, A., Petrucci, L., Schnoebelen, P.: Systems and Software Verification: Model-Checking Techniques and Tools. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-662-04558-9CrossRefMATH

Krahmer, E., van Deemter, K.: Computational generation of referring expressions: a survey. Comput. Linguist. 38(1), 173–218 (2012)CrossRef

Areces, C., Koller, A., Striegnitz, K.: Referring expressions as formulas of description logic. In: Proceedings of the Fifth International Natural Language Generation Conference (INLG 2008), pp. 42–49. Association for Computational Linguistics (2008)

Areces, C., Figueira, S., Gorín, D.: Using logic in the generation of referring expressions. In: Pogodalla, S., Prost, J.-P. (eds.) LACL 2011. LNCS (LNAI), vol. 6736, pp. 17–32. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-22221-4_2CrossRefMATH

Paredaens, J.: On the expressive power of the relational algebra. Inf. Process. Lett. 7(2), 107–111 (1978)MathSciNetCrossRef

Bancilhon, F.: On the completeness of query languages for relational data bases. In: Winkowski, J. (ed.) MFCS 1978. LNCS, vol. 64, pp. 112–123. Springer, Heidelberg (1978). https://doi.org/10.1007/3-540-08921-7_60CrossRef

Arenas, M., Diaz, G.: The exact complexity of the first-order logic definability problem. ACM Trans. Database Syst. 41(2), 13:1–13:14 (2016)MathSciNetCrossRef

Willard, R.: Testing expressibility is hard. In: Proceedings of the 16th International Conference on Principles and Practice of Constraint Programming (CP 2010), pp. 9–23 (2010)CrossRef

10.

Jeavons, P., Cohen, D., Gyssens, M.: How to determine the expressive power of constraints. Constraints 4(2), 113–131 (1999)MathSciNetCrossRef

11.

Areces, C., Campercholi, M., Penazzi, D., Ventura, P.: The complexity of definability by open first-order formulas. Logic J. IGPL (2017, submitted)

12.

Campercholi, M., Vaggione, D.: Semantical conditions for the definability of functions and relations. Algebra Univers. 76(1), 71–98 (2016)MathSciNetCrossRef

13.

Ebbinghaus, H., Flum, J., Thomas, W.: Mathematical Logic. Springer, Heidelberg (1994). https://doi.org/10.1007/978-1-4757-2355-7CrossRefMATH

14.

Gent, I., Jefferson, C., Miguel, I.: MINION: a fast, scalable, constraint solver. In: Proceedings of the 17th European Conference on Artificial Intelligence (ECAI 2006), pp. 98–102. IOS Press (2006)

15.

Zemlyachenko, V.N., Korneenko, N.M., Tyshkevich, R.I.: Graph isomorphism problem. J. Sov. Math. 29(4), 1426–1481 (1985)CrossRef

Title: Deciding Open Definability via Subisomorphisms
Authors: Carlos Areces
Miguel Campercholi
Pablo Ventura
Publisher: Springer Berlin Heidelberg
Book: Logic, Language, Information, and Computation
Print ISBN: 978-3-662-57668-7

Electronic ISBN: 978-3-662-57669-4

Copyright Year: 2018
DOI: https://doi.org/10.1007/978-3-662-57669-4_5

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner