Automatic Sequences

Abstract

Finite automaton is a well known and utilized computational model. Automatic sequences’ definition is bootstraped using the notion of finite automaton. More specifically for the definition we use DFA (Deterministic Finite Automaton) with an output function τ and call it DFAO (Deterministic Finite Automaton with Output). Looking from the Chomsky’s hierarchy of languages it’s exactly the regular type ones that the DFA model recognizes. Using the notion of finite automaton we can show properties such as cross product of automatic sequences and composition of output functions. Relation between morphisms and finite automaton is established for automaticity of a sequence. Using morphisms we can have an alternative way of treating the automatic sequences. Additionally the notion of k−Kernels is introduced and the relation is established with automatic sequences. The interest of finding the algebraicity of formal power series will lead to Christol’s theorem which establishes the relation with automatic sequences, proving another way of representing automatic sequences by the means of formal power series, a notion from the broad field of algebra.

ÖZ: Sonlu otomat, iyi bilinen ve yaygın olarak kullanılan bir hesaplama modelidir. Otomatik dizilerin tanımı, sonlu otomat kavramı kullanılarak elde edilir. Daha spesifik olarak, tezimizde tanım icin çıktı fonksiyonu τ’ya sahip bir DFA (Deterministik Sonlu Otomat) kullanıp ve bunu DFAO (Çikti fonksiyonuna sahip deterministik sonlu otomat) olarak adlandırıyoruz. Chomsky’nin dil hiyerar¸sisine bakıldıgında, DFA modelinin tanıdı ˘ gı diller tam olarak düzenli tipteki dillerdir. Sonlu ˘ otomat kavramını kullanarak, otomatik dizilerin direkt çarpımı ve çıktı fonksiyonlarının birle¸simi gibi özellikleri gösterebiliriz. Dizinin otomatikligi icin ˘ morfizmalarla sonlu otomatlar arasındaki baglantıyı kurarız. Morfizmaları kullanarak ˘ otomatik dizileri incelemenin alternatif bir yolunu elde ederiz. Ayrıca, k−Çekirdek kavramı tanıtılır ve otomatik dizilerle ili¸skisi kurulur. Formal kuvvet serilerinin cebirsel özelliklerini bulma ilgisi, Christol teoremi ile sonuçlanır. Bu teorem, otomatik dizilerle baglantı kurarak, otomatik dizileri formal kuvvet seriler ˘ aracılıgıyla, ba¸ska bir ¸sekilde temsil etmenin mümkün oldu ˘ gunu kanıtlar. Bu, cebirin ˘ geni¸s bir alanından gelen bir kavramdır