Tez No	İndirme	Tez Künye	Durumu
527573		Finite and small-space automata with advice / Öğüt alan sonlu durumlu ve küçük bellekli makineler Yazar:UĞUR KÜÇÜK Danışman: PROF. DR. AHMET CELAL CEM SAY Yer Bilgisi: Boğaziçi Üniversitesi / Fen Bilimleri Enstitüsü / Bilgisayar Mühendisliği Bilim Dalı Konu:Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control Dizin:	Onaylandı Doktora İngilizce 2018 126 s.
Öğüt, bir hesaplama aygıtına bu aygıtın gücünü kendi sınırlarının ötesinde genişle- terek hesaplamasına yardım etmek için sağlanan dış kaynaklı güvenilir bir bilgi parçası- dır. Hesaplanabilir olma kısıtlaması olmayan bu yardımın içeriği tipik olarak yalnızca aygıtın gerçek girdisinin boyutuna bağlıdır ve girdinin esas içeriğinden bağımsızdır. Öğüt alan hesaplamanın özellikleri çeşitli hesaplama modelleri baz alınarak ve karmaşık- lık, çok biçimli hesaplama, formel diller ve sözde rastgelelik gibi farklı kavramlar ile bağlantılı biçimde çalışılagelmiştir. Sonlu durumlu makinalara bu türden harici yardım sağlamak için geliştirilen birkaç model de çeşitli gruplar tarafından çalışılmıştır. Bu araştırma kapsamında iki yeni öğüt alan sonlu durumlu makine modeli tanım- landı: öğüt şeritli sonlu durumlu makineler ve işaretle öğüt alan sonlu durumlu makine- ler. İlk modelde öğüt, bir dizi şeklinde ve girdi şeridinden bağımsız olarak erişilebilen ayrı bir şerit üzerinde sağlanır. İkinci modelde ise öğüt, girdi şeridi üzerine konulan ve iz adı verilen tek biçimli işaretler aracılığı ile sağlanmaktadır. Bu modellerin her birinin hesaplama gücü ve sınırları, temel hesaplama modelinin belirlenimci, olasılıksal ya da kuantum olmasına ve öğütün belirlenimci ya da rastgele biçimde seçilmesine bağlı olarak değişen çeşitli durumlarda incelendi. Artan öğüt miktarının bir hesaplama kaynağı olarak etkileri çeşitli biçimlerde değerlendirmeye dahil edildi. Her bir modelin versiyonları dil tanıma güçleri açısından, kendi aralarında ve daha önceden çalışılmış benzer makine modelleri ile karşılaştırıldı. Bu incelemenin temel sonuçları olarak söz konusu modeller tarafından değişik durumlarda tanınabilen dil sınıfları arasındaki çeşitli ayrışma, örtüşme ve sonsuz sıradüzen ilişkilerinin varlığı gösterildi.
Advice is a piece of trusted supplemental information that is provided to a computing device, in advance of its execution in order to extend its power beyond its limits and hence to assist it in its task. The content of this assistance, which is not restricted to be computable, typically depends only on the length, and not the full content of the actual input to the device. Advised computation has been studied on various computational models and in relation with concepts as diverse as complexity, nonuniform computation, formal languages and pseudorandomness. Several models for providing such external assistance to finite automata have also been studied by various groups. In this research, we introduce two novel models of advised finite automata: finite automata with advice tapes and finite automata with advice inkdots. In the former model advice is provided in the form of a string which is placed on a separate tape accessible independently from the input. In the latter one, we model advice as a set of uniform marks placed on the input tape which are called inkdots. We examine the power and limits of each of these models in a variety of settings where the underlying model of computation is deterministic, probabilistic or quantum and the advice is deterministically or randomly chosen. The roles of increasing amounts of advice as a computational resource are taken into consideration in various forms. The variants of each model are compared with each other and with the previously studied models of advised finite automata in terms of language recognition power. The main results of this analysis are demonstrated by establishing various separations, collapses and infinite hierarchies of the language classes that can be recognized with different models in varying settings.