Logics of metric spaces
Open Access
- 1 April 2003
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Computational Logic
- Vol. 4 (2) , 260-294
Abstract
We investigate the expressive power and computational properties of two different types of languages intended for speaking about distances. First, we consider a first-order language FM the two-variable fragment of which turns out to be undecidable in the class of distance spaces validating the triangular inequality as well as in the class of all metric spaces. Yet, this two-variable fragment is decidable in various weaker classes of distance spaces. Second, we introduce a variable-free modal language MS that, when interpreted in metric spaces, has the same expressive power as the two-variable fragment of FM. We determine natural and expressive fragments of MS which are decidable in various classes of distance spaces validating the triangular inequality, in particular, the class of all metric spaces.Keywords
This publication has 24 references indexed in Scilit:
- On logics with two variablesTheoretical Computer Science, 1999
- Some Logics Related to von Wright's Logic of PlaceNotre Dame Journal of Formal Logic, 1994
- Nominal tense logic.Notre Dame Journal of Formal Logic, 1992
- Using the Universal Modality: Gains and QuestionsJournal of Logic and Computation, 1992
- Logics and models of real time: A survey1992
- Semantics of Horn and disjunctive logic programsTheoretical Computer Science, 1991
- Expressive Functional Completeness in Tense Logic (Preliminary report)1981
- A note on the logic of elsewhereTheoria, 1980
- On languages with two variablesMathematical Logic Quarterly, 1975
- Topological LogicThe Journal of Symbolic Logic, 1969