On the computability of region-based euclidean logics

Yavor Nenov, Ian Pratt-Hartmann

    Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

    Abstract

    By a Euclidean logic, we understand a formal language whose variables range over subsets of Euclidean space, of some fixed dimension, and whose non-logical primitives have fixed meanings as geometrical properties, relations and operations involving those sets. In this paper, we consider first-order Euclidean logics with primitives for the properties of connectedness and convexity, the binary relation of contact and the ternary relation of being closer-than. We investigate the computational properties of the corresponding first-order theories when variables are taken to range over various collections of subsets of 1-, 2- and 3-dimensional space. We show that the theories based on Euclidean spaces of dimension greater than 1 can all encode either first- or second-order arithmetic, and hence are undecidable. We show that, for logics able to express the closer-than relation, the theories of structures based on 1-dimensional Euclidean space have the same complexities as their higher-dimensional counterparts. By contrast, in the absence of the closer-than predicate, all of the theories based on 1-dimensional Euclidean space considered here are decidable, but non-elementary. © 2010 Springer-Verlag Berlin Heidelberg.
    Original languageEnglish
    Title of host publicationLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)|Lect. Notes Comput. Sci.
    Place of PublicationHeidelberg
    PublisherSpringer Nature
    Pages439-453
    Number of pages14
    Volume6247
    ISBN (Print)364215204X, 9783642152047
    DOIs
    Publication statusPublished - 2010
    Event24th International Workshop on Computer Science Logic, CSL 2010, and 19th Annual Conference of the EACSL - Brno
    Duration: 1 Jul 2010 → …

    Conference

    Conference24th International Workshop on Computer Science Logic, CSL 2010, and 19th Annual Conference of the EACSL
    CityBrno
    Period1/07/10 → …

    Fingerprint

    Dive into the research topics of 'On the computability of region-based euclidean logics'. Together they form a unique fingerprint.

    Cite this