Finite and Small-Space Automata with Advice
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.
Özet:
Öğüt, bir hesaplama aygıtına bu aygıtın gücünü kendi sınırlarının ötesinde genişleterek hesaplamasına yardım etmek i¸cin sağlanan dı¸s kaynaklı g¨uvenilir bir bilgi par¸casıdır. Hesaplanabilir olma kısıtlaması olmayan bu yardımın i¸ceriği tipik olarak yalnızca aygıtın ger¸cek girdisinin boyutuna bağlıdır ve girdinin esas i¸ceriğinden bağımsızdır. Öğüt alan hesaplamanın ¨ozellikleri ¸ce¸sitli hesaplama modelleri baz alınarak ve karma¸sık- ¨ lık, ¸cok bi¸cimli hesaplama, formel diller ve s¨ozde rastgelelik gibi farklı kavramlar ile bağlantılı bi¸cimde ¸calı¸sılagelmi¸stir. Sonlu durumlu makinalara bu t¨urden harici yardım sağlamak i¸cin geli¸stirilen birka¸c model de ¸ce¸sitli gruplar tarafından ¸calı¸sılmı¸stır. Bu ara¸stırma kapsamında iki yeni ¨oğ¨ut alan sonlu durumlu makine modeli tanımlandı: oğüt ¸seritli sonlu durumlu makineler ve i¸saretle oğüt alan sonlu durumlu makineler. ˙Ilk modelde ¨o˘g¨ut, bir dizi ¸seklinde ve girdi ¸seridinden bağımsız olarak eri¸silebilen ayrı bir ¸serit ¨uzerinde sağlanır. ˙Ikinci modelde ise öğüt, girdi ¸seridi ¨uzerine konulan ve iz adı verilen tek bi¸cimli i¸saretler aracılı˘gı ile sa˘glanmaktadır. Bu modellerin her birinin hesaplama g¨uc¨u ve sınırları, temel hesaplama modelinin belirlenimci, olasılıksal ya da kuantum olmasına ve oğütün belirlenimci ya da rastgele bi¸cimde se¸cilmesine ba˘glı olarak de˘gi¸sen ¸ce¸sitli 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¨u¸cleri a¸cısından, kendi aralarında ve daha ¨onceden ¸calı¸sılmı¸s benzer makine modelleri ile kar¸sıla¸stırıldı. Bu incelemenin temel sonu¸cları olarak s¨oz konusu modeller tarafından deği¸sik durumlarda tanınabilen dil sınıfları arasındaki ¸ce¸sitli ayrı¸sma, ¨ort¨u¸sme ve sonsuz sırad¨uzen ili¸skilerinin varlı˘gı g¨osterildi.