On linear order and computation : The expressiveness of interactive computations on linear orders and computations indexed by ordinals

Show simple item record

dc.contributor Helsingin yliopisto, matemaattis-luonnontieteellinen tiedekunta, matematiikan ja tilastotieteen laitos fi
dc.contributor Helsingfors universitet, matematisk-naturvetenskapliga fakulteten, matematiska och statistiska institutionen sv
dc.contributor University of Helsinki, Faculty of Science, Department of Mathematics and Statistics en
dc.contributor MALJA graduate school in Algebra, Set Theory, Logic and analysis, Model theory, and Finite model theory en
dc.contributor The Finite Model Theory group en
dc.contributor The Helsinki logic group. en
dc.contributor.author Bissell-Siders, Ryan
dc.date.accessioned 2010-11-25T12:09:40Z
dc.date.available 2010-11-25T12:09:40Z
dc.date.issued 2008-11-21
dc.identifier.uri URN:ISBN:978-952-10-5089-3 fi
dc.identifier.uri http://hdl.handle.net/10138/21260
dc.description.abstract We solve the Dynamic Ehrenfeucht-Fra\"iss\'e Game on linear orders for both players, yielding a normal form for quantifier-rank equivalence classes of linear orders in first-order logic, infinitary logic, and generalized-infinitary logics with linearly ordered clocks. We show that Scott Sentences can be manipulated quickly, classified into local information, and consistency can be decided effectively in the length of the Scott Sentence. We describe a finite set of linked automata moving continuously on a linear order. Running them on ordinals, we compute the ordinal truth predicate and compute truth in the constructible universe of set-theory. Among the corollaries are a study of semi-models as efficient database of both model-theoretic and formulaic information, and a new proof of the atomicity of the Boolean algebra of sentences consistent with the theory of linear order -- i.e., that the finitely axiomatized theories of linear order are dense. en
dc.description.abstract Lineaarijärjestysten kvanttoriastehierarkiassa olemme onnistunut laskemaan varsin tarkasti tiettyyn kvanttoriasteeseen asti ei-ekvilaenttien lineaarijärjesysten äärellisen lukumäärän. Ääretöaikaisten koneiden malleistä näimme että Turing-kone ja päättymät automaatteja pystyvät Gödelin konstruoituvan universumin laskemiseen. fi
dc.language.iso en
dc.publisher Helsingin yliopisto fi
dc.publisher Helsingfors universitet sv
dc.publisher University of Helsinki en
dc.relation.isformatof URN:ISBN:978-952-10-5088-6 fi
dc.relation.isformatof Helsinki: 2008 fi
dc.rights Julkaisu on tekijänoikeussäännösten alainen. Teosta voi lukea ja tulostaa henkilökohtaista käyttöä varten. Käyttö kaupallisiin tarkoituksiin on kielletty. fi
dc.rights This publication is copyrighted. You may download, display and print it for Your own personal use. Commercial use is prohibited. en
dc.rights Publikationen är skyddad av upphovsrätten. Den får läsas och skrivas ut för personligt bruk. Användning i kommersiellt syfte är förbjuden. sv
dc.subject matematiikka fi
dc.title On linear order and computation : The expressiveness of interactive computations on linear orders and computations indexed by ordinals en
dc.type.ontasot Väitöskirja (artikkeli) fi
dc.type.ontasot Doctoral dissertation (article-based) en
dc.type.ontasot Doktorsavhandling (sammanläggning) sv
dc.ths Väänänen, Jouko
dc.opn Hella, Lauri
dc.type.dcmitype Text

Files in this item

Total number of downloads: Loading...

Files Size Format View
onlinear.pdf 791.8Kb PDF View/Open

This item appears in the following Collection(s)

Show simple item record