Arşiv ve Dokümantasyon Merkezi
Dijital Arşivi

Finite and small - space automata with advice

Basit öğe kaydını göster

dc.contributor Ph.D. Program in Computer Engineering.
dc.contributor.advisor Say, Ahmet Celal Cem.
dc.contributor.author Küçük, Uğur.
dc.date.accessioned 2023-03-16T10:13:52Z
dc.date.available 2023-03-16T10:13:52Z
dc.date.issued 2018.
dc.identifier.other CMPE 2018 K83 PhD
dc.identifier.uri http://digitalarchive.boun.edu.tr/handle/123456789/12626
dc.description.abstract 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.
dc.format.extent 30 cm.
dc.publisher Thesis (Ph.D.) - Bogazici University. Institute for Graduate Studies in Science and Engineering, 2018.
dc.subject.lcsh Machine theory.
dc.title Finite and small - space automata with advice
dc.format.pages xvii, 109 leaves ;


Bu öğenin dosyaları

Bu öğe aşağıdaki koleksiyon(lar)da görünmektedir.

Basit öğe kaydını göster

Dijital Arşivde Ara


Göz at

Hesabım