Watson-Crick (abbreviated as WK) finite automata are working on double stranded
DNA molecule that is also called Watson-Crick tape. Subsequently, these automata
have two reading heads, one for each strand. While in traditional WK automata both
heads read the whole input in the same physical direction, in 5
′ → 3′ WK automata
the heads start from the two extremes (say 5
′
end of the strands) and read the input in
opposite direction. In sensing 5
′ → 3′ WK automata the process on the input is finished
when the heads meet. Since the heads of a WK automaton may read longer strings in
a transition, in previous models a so-called sensing parameter took care for the proper
meeting of the heads (not allowing to read the same positions of the input in the last
step). We have investigated a new model which works without the sensing parameter
(it is done by an appropriate change of the concept of the configuration). In this thesis,
the nondeterministic and deterministic automata in the new model are studied.
Consequently, for the nondeterministic part, the accepted language classes of variants
are changed and various hierarchy results are proven. For the deterministic part, it is
proven to accept the language class 2detLIN defined by the deterministic variant of
the earlier version. However, using some of the restricted variants, e.g., all-final
automata, the classes of the accepted languages are changed showing a finer hierarchy
inside the class of linear context-free languages, hierarchy.
Keywords: nondeterministic Watson-Crick automata, deterministic Watson-Crick
automata, 5
′ → 3′ WK automata, finite automata, deterministic computations, linear
context-free languages.
ÖZ:Watson-Crick (WK olarak kısaltılmıştır) sonlu otomataları, Watson-Crick bandı
olarak da adlandırılan çift sarmallı DNA molekülü üzerinde çalışmaktadır. Bundan
dolayı, bu otomatalar her bir tel için birer tane olmak üzere iki okuma kafasına sahiptir.
Geleneksel WK otomatlarında her iki kafa da tüm girişi aynı fiziksel yönde okurken,
5
′ → 3′ WK otomatlarında kafalar iki uçtan başlar (iplikçiklerin 5 ′ ucu gibi) ve girişi
ters yönde okur. 5
′ → 3′ WK otomat algılamasında, kafalar buluştuğunda girişteki
işlem tamamlanır. Bir WK otomatının kafaları bir geçişte daha uzun dizeler
okuyabildiğinden, önceki modellerde, kafaların düzgün bir şekilde toplanması için bir
algılama parametresi kullanıldı (son adımda girişin aynı pozisyonlarını okumaya izin
vermiyor). Algılama parametresi olmadan çalışan yeni bir model araştırdık
(konfigürasyon kavramının uygun bir şekilde değiştirilmesi ile yapılır). Bu tezde yeni
modeldeki deterministik ve deterministik olmayan otomatlar incelenmiştir. Sonuç
olarak, deterministik olmayan kısım için, varyantların kabul edilen dil sınıfları
değiştirilir ve çeşitli hiyerarşi sonuçları kanıtlanır. Deterministik kısım için, önceki
versiyonun deterministik varyantı tarafından tanımlanan 2detLIN dil sınıfını kabul
ettiği kanıtlanmıştır. Bununla birlikte, kısıtlı varyantların bazıları, örn., Tümüyle son
otomatik veriler kullanılarak, kabul edilen dillerin sınıfları, doğrusal bağlamsız diller,
hiyerarşi sınıfında daha ince bir hiyerarşi gösterecek şekilde değiştirilir.
Anahtar Kelimeler: Deterministik olmayan Watson-Crick otomatları, deterministik
Watson-Crick otomatları, 5
′ → 3′ WK otomatları, sonlu otomatlar, deterministik
hesaplamalar, doğrusal bağlamdan bağımsız diller.
