Picture languages and locality

Show full item record


Title: Picture languages and locality
Author: Tukiainen, Simo
Contributor: University of Helsinki, Faculty of Science
Publisher: Helsingin yliopisto
Date: 2020
Language: eng
URI: http://urn.fi/URN:NBN:fi:hulib-202008173794
Thesis level: master's thesis
Discipline: Matematiikka
Abstract: In this master's thesis we study the generalization of word languages into multi-dimensional arrays of letters i.e picture languages. Our main interest is the class of recognizable picture languages which has many properties in common with the robust class of regular word languages. After surveying the basic properties of picture languages, we present a logical characterization of recognizable picture languages—a generalization of Büchi's theorem of word languages into pictures, namely that the class of recognizable picture languages is the one recognized by existential monadic second-order logic. The proof presented is a recent one that makes the relation between tilings and logic clear in the proof. By way of the proof we also study the locality of the model theory of picture structures through logical locality obtained by normalization of EMSO on those structures. A continuing theme in the work is also to compare automata and recognizability between word and picture languages. In the fourth section we briefly look at topics related to computativity and computational complexity of recognizable picture languages.
Subject: picture languages
recognizable picture languages
existential second-order logic
finite model theory
cellular automata

Files in this item

Total number of downloads: Loading...

Files Size Format View
gradu-20200617-final.pdf 408.8Kb PDF View/Open

This item appears in the following Collection(s)

Show full item record