|
EMU I-REP >
08 Faculty of Arts and Sciences >
Department of Mathematics >
Theses (Master's and Ph.D) – Mathematics >
Please use this identifier to cite or link to this item:
http://hdl.handle.net/11129/6319
|
Title: | Automatic Sequences |
Authors: | Nagy, Benedek (Supervisor) Cakolli, Fatlonder Eastern Mediterranean University, Faculty of Arts and Sciences, Dept. of Mathematics |
Keywords: | Mathematics Department Sequences (Mathematics) |
Issue Date: | Jul-2023 |
Publisher: | Eastern Mediterranean University (EMU) - Doğu Akdeniz Üniversitesi (DAÜ) |
Citation: | Cakolli, Fatlonder. (2023). Automatic Sequences. Thesis (M.S.), Eastern Mediterranean University, Institute of Graduate Studies and Research, Dept. of Mathematics, Famagusta: North Cyprus. |
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 |
Description: | Master of Science in Applied Mathematics and Computer Science. Institute of Graduate Studies and Research. Thesis (M.S.) - Eastern Mediterranean University, Faculty of Arts and Sciences, Dept. of Mathematics, 2023. Supervisor: Prof. Dr. Benedek Nagy. |
URI: | http://hdl.handle.net/11129/6319 |
Appears in Collections: | Theses (Master's and Ph.D) – Mathematics
|
This item is protected by original copyright
|
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.
|