Real-Time Vector Automata

Summary:

Finite automaton has been one of the most studied models in automata theory. The limited power of the standard model has led researchers to make various extensions to the standard model. Counter automaton, automaton with multiplication, finite automaton over groups are some of the examples of such extensions. In this thesis, we study the computational power of real-time finite automaton that has been augmented with a vector of dimension $k$, and programmed to multiply this vector at each step by an appropriately selected kxk matrix. Only one entry of the vector can be tested for equality to 1 at any time. We study the classes of languages recognized by deterministic, nondeterministic, and ``blind'' versions of these machines and compare them with each other. It turns out that these machines are closely related to some of the classical models like counter automata and generalized finite automata.

Özet:

Sonlu durum makinesi otomata teorisinin en çok incelenen modellerinden biri olmuştur. Standart modelin gücünün sınırlı olması araştırmacıları bu standart modelin üzerine farklı eklemeler yapmaya itmiştir. Sayaçlı makineler, çarpımlı sonlu durum makineleri, grup üzerinde tanımlı sonlu durum makineleri bu eklemelere örnektir. Bu tezde $ k $ boyutlu bir vektörle güçlendirilmiş ve her adımda bu vektörü uygun kxk matrislerle çarpmaya programlanmış gerçek zamanlı sonlu durum makineleri incelenmiştir. Bir adımda vektörün sadece tek bir girdisi 1'e eşit mi diye kontrol edilebilir. Makinelerin belirlenimci, belirlenimci olmayan, ``kör'' versiyonları tarafından tanınan diller incelenmiş ve birbirleriyle karşılaştırılmışlardır. Bu makineler ile, sayaçlı makinelerin ve genellenmiş sonlu durum makinelerin birbirleriyle yakından ilişkili olduğu ortaya çıkmıştır.