DSpace
 

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

Files in This Item:

File Description SizeFormat
CakolliFatlonder-Master.pdfThesis, Master237.07 kBAdobe PDFView/Open


This item is protected by original copyright

Recommend this item
View Statistics

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.

 

Valid XHTML 1.0! DSpace Software Copyright © 2002-2010  Duraspace - Feedback