Locality and order-invariant logics

Show full item record



Permalink

http://urn.fi/URN:ISBN:978-952-10-4428-1
Title: Locality and order-invariant logics
Author: Niemistö, Hannu
Contributor: University of Helsinki, Faculty of Science, Department of Mathematics and Statistics
Publisher: University of Helsinki
Date: 2007-12-18
Language: en
URI: http://urn.fi/URN:ISBN:978-952-10-4428-1
http://hdl.handle.net/10138/21273
Thesis level: Doctoral dissertation (monograph)
Abstract: Malli on logiikassa käytetty abstraktio monille matemaattisille objekteille. Esimerkiksi verkot, ryhmät ja metriset avaruudet ovat malleja. Äärellisten mallien teoria on logiikan osa-alue, jossa tarkastellaan logiikkojen, formaalien kielten, ilmaisuvoimaa malleissa, joiden alkioiden lukumäärä on äärellinen. Rajoittuminen äärellisiin malleihin mahdollistaa tulosten soveltamisen teoreettisessa tietojenkäsittelytieteessä, jonka näkökulmasta logiikan kaavoja voidaan ajatella ohjelmina ja äärellisiä malleja niiden syötteinä. Lokaalisuus tarkoittaa logiikan kyvyttömyyttä erottaa toisistaan malleja, joiden paikalliset piirteet vastaavat toisiaan. Väitöskirjassa tarkastellaan useita lokaalisuuden muotoja ja niiden säilymistä logiikkoja yhdistellessä. Kehitettyjä työkaluja apuna käyttäen osoitetaan, että Gaifman- ja Hanf-lokaalisuudeksi kutsuttujen varianttien välissä on lokaalisuuskäsitteiden hierarkia, jonka eri tasot voidaan erottaa toisistaan kasvavaa dimensiota olevissa hiloissa. Toisaalta osoitetaan, että lokaalisuuskäsitteet eivät eroa toisistaan, kun rajoitutaan tarkastelemaan äärellisiä puita. Järjestysinvariantit logiikat ovat kieliä, joissa on käytössä sisäänrakennettu järjestysrelaatio, mutta sitä on käytettävä siten, etteivät kaavojen ilmaisemat asiat riipu valitusta järjestyksestä. Määritelmää voi motivoida tietojenkäsittelyn näkökulmasta: vaikka ohjelman syötteen tietojen järjestyksellä ei olisi odotetun tuloksen kannalta merkitystä, on syöte tietokoneen muistissa aina jossakin järjestyksessä, jota ohjelma voi laskennassaan hyödyntää. Väitöskirjassa tutkitaan minkälaisia lokaalisuuden muotoja järjestysinvariantit ensimmäisen kertaluvun predikaattilogiikan laajennukset yksipaikkaisilla kvanttoreilla voivat toteuttaa. Tuloksia sovelletaan tarkastelemalla, milloin sisäänrakennettu järjestys lisää logiikan ilmaisuvoimaa äärellisissä puissa.A model is an abstraction used in mathematical logic for various objects in mathematics. For example, graphs, groups and metric spaces are models. Finite model theory is a part of logic that considers the expressive power of different logics on models with finitely many elements. By restricting the cardinality of the models, the results can be applied to theoretical computer science: formulas can be thought as programs and models as inputs to these programs. Locality means the inability of the logic to separate models with matching local features. In this thesis, we study various forms of locality and their conservation when combining logics. The results are used to define a hierarchy of locality notions between Gaifman- and Hanf-locality. The levels of the hierarchy are seprarated by grids of increasing dimension. On the other hand, we show that the locality hierarchy collapses on finite trees. Order-invariant logics are logics with a built-in linear order, that can be used only in such a way that the things expressed by formulas do not depend on the chosen order. The concept can be motivated from the perspective of computer science: the input of a program is always ordered in the memory of the computer even if the results are not supposed to depend on the order. However, the order may help the program to compute the result. We show that certain order-invariant first-order logics extended with a unary quantifier satisfy some forms of locality. The results are used to find when the built-in linear order increases the expressive power of the logics on finite trees.
Subject: matematiikka
Rights: This publication is copyrighted. You may download, display and print it for Your own personal use. Commercial use is prohibited.


Files in this item

Total number of downloads: Loading...

Files Size Format View
locality.pdf 821.2Kb PDF View/Open

This item appears in the following Collection(s)

Show full item record