Extended models of finite automata
Güçlendirilmiş sonlu durumlu makine modelleri
- Tez No: 587884
- Danışmanlar: PROF. DR. AHMET CELAL CEM SAY
- Tez Türü: Doktora
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2019
- Dil: İngilizce
- Üniversite: Boğaziçi Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 162
Özet
Literatürde ortaya sürülmüş olan pek çok makine, bir sonlu durumlu makinenin ek bir hafıza ünitesi ile güçlendirilmiş hali olarak düşünülebilir. Bu tezde, bu makine-\newline lerden ikisine, gruplar üzerinde tanımlı sonlu durumlu makinelere ve eve dönen vektör makinelerine odaklanılmıştır. $ G $ grubu üzerinde tanımlı bir makine, sahip olduğu ek hafıza ünitesinde $ G $ grubundan bir elemanı tutma hakkına sahip, belirlenimci olmayan bir sonlu durumlu makinedir. Başlangıçta hafıza ünitesinin değeri $ G $ grubunun birim elemanıdır. Bir hesaplamanın başarılı sayılabilmesi için hafıza ünitesinin değerinin, her adımda grubun bir elemanıyla çarpıldıktan sonra bitimde grubun birim elemanına eşit olması beklenir. Bu çalışmada tam sayılı ve rasyonel sayılı matris grupları üzerinde tanımlanan sonlu durumlu makine-\newline ler incelenmiş, bu makinelerin tanıdığı dil sınıflarının birbirleri ile olan ilişkileri ortaya çıkarılmıştır. Grubun büyüme hızı, makinelerin çalışma süresi gibi çeşitli parametrelere bakılarak, bu parametrelerin makinelerin tanıma gücünü nasıl etkilediği araştırılmıştır. Matris yarıgruplarının karar verme problemleri ile ilintili makinelerin karar verme problemleri arasında bir bağ kurulmuştur. Grup üzerinde tanımlı makinelerle yakından ilişkili olan bazı modeller incelenmiş ve bir takım yeni sonuçlar elde edilmiştir. Yeni tanımladığımız eve dönen vektör makinesi, bir sonlu durumlu makinenin bir vektörle güçlendirilmesi ve makineye bu vektörü her adımda bir matrisle çarpma hakkı verilmesiyle ortaya çıkmıştır. Makinenin vektörün başlangıç vektörüne eşit olup olmadığını kontrol etme hakkı vardır ve makinenin kabul şartı, hesaplama bittiğinde vektörün başlangıç vektörüne eşit olması ve kabul durumlarından birinde bulunulmasıdır. Kullanılan matris kümesi sınırlanarak ve vektörün eşitlik kontrolünün sadece en sonda gerçekleşmesine izin verilerek, farklı kısıtlamaların makineye olan etkisi incelenmiştir. Makinenin çeşitli sürümleri tanımlanarak, bu modellerin dil tanıma gücüyle klasik modellerin dil tanıma gücü karşılaştırılmıştır. Matris grupları üzerinde tanımlı sonlu durumlu makinelerle, bir yönlü belirlenimci olmayan kör eve dönen vektör maki-\newline neleri arasında ilişki kurularak eve dönen vektör makineleri ile ilgili yeni sonuçlar elde edilmiştir. Gerçek zamanlı eve dönen vektör makineleri üzerinde özellikle durulmuş, bazı kapalılık özellikleri gösterilmiş ve bu makinelerin tek durumlu versiyonları analiz edilmiştir. Stern-Brocot ağacından faydalanarak dizgeleri vektörlere kodlamaya yarayan bir metod geliştirilmiştir.
Özet (Çeviri)
Many of the numerous automaton models proposed in the literature can be regarded as a finite automaton equipped with an additional storage mechanism. In this thesis, we focus on two such models, namely the finite automata over groups and the homing vector automata. A finite automaton over a group $ G $ is a nondeterministic finite automaton equipped with a register that can hold an element of the group $ G $. Initially the register is initialized to the identity element of the group and a computation is successful if the register is equal to the identity element at the end of the computation after being multiplied with a group element at every step. We investigate the language recognition power of finite automata over integer and rational matrix groups and reveal new relationships between the language classes corresponding to these models. We look at various parameters such as the growth rate of the groups and the run-time of the machines, to discover the effects of these parameters on the language recognition power. We establish a link between the decision problems of matrix semigroups and the decision problems of corresponding automata. We look at some computational models which are closely related to finite automata over groups, namely the valence pushdown automata and the context-free valence grammars and present some new results. We also propose the new homing vector automaton model, which is a finite automaton equipped with a vector, and which can multiply this vector with an appropriate matrix at each step. The vector can be checked for equivalence to the initial vector and the acceptance criterion is ending up in an accept state with the value of the vector being equal to the initial vector. We examine the effect of various restrictions on the model by confining the matrices to a particular set and allowing the equivalence test only at the end of the computation. We define the different variants of the model and compare their language recognition power with that of the classical models. We establish a link between finite automata over matrix groups and one-way nondeterministic blind homing vector automata which extends our knowledge on the latter. We pay special attention to real-time homing vector automata and analyze their stateless versions and closure properties. We develop a method for encoding strings into vectors, based on the Stern-Brocot Tree, which may be of independent interest.
Benzer Tezler
- Analysis of extended feature models with constraint programming
Genişletilmiş özellik modellerinin kısıt programlama ile analizi
AHMET SERKAN KARATAŞ
Doktora
İngilizce
2010
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolOrta Doğu Teknik ÜniversitesiBilgisayar Mühendisliği Bölümü
DOÇ. DR. ALİ DOĞRU
DOÇ. DR. HALİT OĞUZTÜZÜN
- Dynamic analysis of hydraulic cylinder
Hidrolik silindirin dinamik analizi
KUTLAY AKSÖZ
Yüksek Lisans
İngilizce
2004
Makine MühendisliğiDokuz Eylül ÜniversitesiMakine Mühendisliği Ana Bilim Dalı
PROF.DR. HİRA KARAGÜLLE
- Yuvarlak örme makinesi elemanlarının aşınma ve dinamik davranışının modellenmesi
Modeling of abrasion and dynamic behaviour of circular knitting elements
SENA DURU
Doktora
Türkçe
2016
Makine Mühendisliğiİstanbul Teknik ÜniversitesiTekstil Mühendisliği Ana Bilim Dalı
PROF. DR. CEVZA CANDAN
PROF. DR. ATA MUĞAN
- Altı boyutlu ising modelinin 'Creutz cellular automaton'ında incelenmesi
Study of the six-dimensional ising model on the 'Creutz cellular automaton'
ZİYA MERDAN
Doktora
Türkçe
2003
Fizik ve Fizik MühendisliğiGazi ÜniversitesiFizik Ana Bilim Dalı
PROF. DR. NEVZAT AKTEKİN
- A compressed sensing based approach on discrete algebraic reconstruction technique
Ayrık cebirsel geriçatma tekniği için sıkıştırılmış algılama esaslı bir yaklaşım
EZGİ DEMİRCAN TÜREYEN
Yüksek Lisans
İngilizce
2015
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DOÇ. DR. MUSTAFA ERSEL KAMAŞAK