Two-way finite automata with advice
Öğüt alan çift yönlü sonlu makineler
- Tez No: 882810
- Danışmanlar: PROF. AHMET CELAL CEM SAY
- Tez Türü: Yüksek Lisans
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2024
- Dil: İngilizce
- Üniversite: Boğaziçi Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 31
Özet
Bir hesaplama modeline karakter dizisi formatında dışarıdan yapılan güvenilir yardıma öğüt denir. Öğüt alan makineler, Damm ve Holzer'ın makalesinden itibaren çalışılmaktadır. Yakın zamanda Küçük ve ark. öğütün girdinin önüne eklendiği eski usulden farklı olarak öğütün ayrı bir teypte durduğu ve özel bir öğüt kafasıyla erişildiği yeni bir öğütlü makine modeli ortaya attılar. Biz de bu çalışmada Küçük ve ark.'nın tanımladığı bu modeli (ilk kez çoklu girdi kafaları özelliğini de ekleyerek) çalışacağız. Girdi boyunun öğüt boyunun bir polinomu ile sınırlı olduğu ve öğüt boyunun da girdi boyunun bir polinomu ile sınırlı olduğu, ayrıca tüm kafaların çift yönlü olduğu makineler için girdi kafaları ile öğüt kafaları arasında bir alışveriş imkanı olduğunu göstereceğiz. Frei ve ark. öğüt boyunun yeterince yavaş arttığı durumlarda tek yönlü bir girdi kafası ve çift yönlü bir öğüt kafasına sahip belirlenimci sonlu makinelere ne belirlen- imcilik kısıtını kaldırmanın, ne girdi kafasına çift yönlü hareket serbestliği tanımanın, ne de herhangi bir sayıda çift yönlü öğüt kafası eklemenin yardım edebileceğini iddia etti. Bu iddianın kanıtı olarak önerilen argümandaki hatayı gösterip iddianın aksini kanıtlayacağız. Öğüt miktarının sabit olmadığı her durumda tek yönlü bir girdi kafası ve tek yönlü bir öğüt kafasına sahip belirlenimci olmayan makinelerin bile tek yönlü bir girdi kafasına ve herhangi bir sayıda çift yönlü öğüt kafasına sahip belirlenimci makinelerce tanınamayan bir dili tanıdığını göstereceğiz. Frei ve ark. ayrıca L/poly problem sınıfının öğüt alan sonlu makineler cinsin- den bir karakterizasyonunu geliştirdiklerini iddia ettiler. Bu iddianın kanıtında tespit ettiğimiz bir problemi göstereceğiz.
Özet (Çeviri)
Advice is trusted external assistance provided to a model of computation in the form of strings. Automata with advice has been studied since the work of Damm and Holzer. Recently Küçük et al. defined a model of advised automata where the advice string is put in a separate tape with its own dedicated head instead of appended in the beginning of input which had been the usual convention before. In this work we will adopt the model defined by Küçük et al. and introduce multiple input heads into it, which has not been done before. We show that it is possible to trade input heads with advice heads and vice versa when all heads are two-way and advice length is bounded by a polynomial function of input length and input length is bounded by a polynomial function of advice length. Frei et al. claimed that for short advices (whose logarithm grows slower than logarithm of logarithm of input length) neither non-determinism, nor two-way move- ment capability of input head, nor arbitrary number of additional advice heads (nor any combination of these) can help to deterministic automata with one one-way input head and one two-way advice head. We disprove this claim, and point to the error in the proposed proof. Specifically, we prove that as long as advice is more than constant, even the set of non-deterministic automata with one one-way input head and one one- way advice head recognize languages that are not recognizable by any deterministic automata with one one-way input head and any number of two-way advice heads. Frei et al. also claimed an improvement over the characterization of the problem class L/poly with automata that take advice by Holzer. We identify a mistake in the proposed proof of a lemma on which their result depends.
Benzer Tezler
- Kısaltıcı mekanizmasının bir boyutlu hücresel hareketlilerde gerçek zamanda simülasyonu
The Simulation of shrinkers by one dimensional cellular automata in real time
ZEKİ ÇİFTÇİ
Doktora
Türkçe
2002
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolGazi ÜniversitesiElektronik ve Bilgisayar Eğitimi Ana Bilim Dalı
PROF. DR. DOĞAN ÇALIKOĞLU
- 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
- Design and simulation of two-way quantum finite automata
Kuantum çift yönlü sonlu durum makinelerinin dizayn ve simulasyonu
FATİH MEHMET ATAK
Yüksek Lisans
İngilizce
2006
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolBoğaziçi ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
PROF.DR. CEM SAY
- Extended models of finite automata
Güçlendirilmiş sonlu durumlu makine modelleri
ÖZLEM SALEHİ KÖKEN
Doktora
İngilizce
2019
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