Finite and small-space automata with advice
Öğüt alan sonlu durumlu ve küçük bellekli makineler
- Tez No: 527573
- Danışmanlar: PROF. DR. AHMET CELAL CEM SAY
- Tez Türü: Doktora
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2018
- Dil: İngilizce
- Üniversite: Boğaziçi Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Bilgisayar Mühendisliği Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 126
Özet
Öğü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.
Özet (Çeviri)
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.
Benzer Tezler
- Classical and quantum computation with small space bounds
Az belleğe sahip klasik ve kuantum hesaplama
ABUZER YAKARYILMAZ
Doktora
İngilizce
2011
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolBoğaziçi ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
PROF. DR. AHMET CELAL CEM SAY
- Karma sistemlerin tümleyen değişkenli modelleri
Complementarity modeling of hybrid system
SELİM TÜRKYILMAZ
Yüksek Lisans
Türkçe
1999
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiElektronik ve Haberleşme Mühendisliği Ana Bilim Dalı
DOÇ. DR. KÜLMİZ ÇEVİK
- Bir deri kesme presinin temel tasarımı ve kontrolü
Main construction of a leather cutting press and its control
HAKAN ASLAN
- Dikey dairesel silindirik açık su havuzlarında hidrodinamik kuvvetler
Hydrodynamic forces for vertical axis circular cylinder containing a concertric cylindrical hole in finite depth
MÜKERREM ERTEN(İLKIŞIK)
- Computational analysis of external store carriage in transonic speed regime
Harici yük taşımanın transonik sürat bölgesinde hesaplamalı analizi
İ. CENKER ASLAN
Yüksek Lisans
İngilizce
2003
Havacılık Mühendisliğiİstanbul Teknik ÜniversitesiUçak Mühendisliği Ana Bilim Dalı
DOÇ. DR. AYDIN MISIRLIOĞLU
PROF. DR. OKTAY BAYSAL