Geri Dön

Finite and small-space automata with advice

Öğüt alan sonlu durumlu ve küçük bellekli makineler

  1. Tez No: 527573
  2. Yazar: UĞUR KÜÇÜK
  3. Danışmanlar: PROF. DR. AHMET CELAL CEM SAY
  4. Tez Türü: Doktora
  5. Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
  6. Anahtar Kelimeler: Belirtilmemiş.
  7. Yıl: 2018
  8. Dil: İngilizce
  9. Üniversite: Boğaziçi Üniversitesi
  10. Enstitü: Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Bilgisayar Mühendisliği Bilim Dalı
  12. Bilim Dalı: Belirtilmemiş.
  13. 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

  1. Classical and quantum computation with small space bounds

    Az belleğe sahip klasik ve kuantum hesaplama

    ABUZER YAKARYILMAZ

    Doktora

    İngilizce

    İngilizce

    2011

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolBoğaziçi Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    PROF. DR. AHMET CELAL CEM SAY

  2. Karma sistemlerin tümleyen değişkenli modelleri

    Complementarity modeling of hybrid system

    SELİM TÜRKYILMAZ

    Yüksek Lisans

    Türkçe

    Türkçe

    1999

    Elektrik ve Elektronik Mühendisliğiİstanbul Teknik Üniversitesi

    Elektronik ve Haberleşme Mühendisliği Ana Bilim Dalı

    DOÇ. DR. KÜLMİZ ÇEVİK

  3. Bir deri kesme presinin temel tasarımı ve kontrolü

    Main construction of a leather cutting press and its control

    HAKAN ASLAN

    Yüksek Lisans

    Türkçe

    Türkçe

    1992

    Makine Mühendisliğiİstanbul Teknik Üniversitesi

    PROF. DR. A. TALHA DİNİBÜTÜN

  4. 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)

    Doktora

    Türkçe

    Türkçe

    1988

    Gemi Mühendisliğiİstanbul Teknik Üniversitesi

    PROF.DR. KEMAL KAFALI

  5. 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

    İngilizce

    2003

    Havacılık Mühendisliğiİstanbul Teknik Üniversitesi

    Uçak Mühendisliği Ana Bilim Dalı

    DOÇ. DR. AYDIN MISIRLIOĞLU

    PROF. DR. OKTAY BAYSAL