Tez No	İndirme	Tez Künye	Durumu
123571	Bu tezin, veri tabanı üzerinden yayınlanma izni bulunmamaktadır. Yayınlanma izni olmayan tezlerin basılı kopyalarına Üniversite kütüphaneniz aracılığıyla (TÜBESS üzerinden) erişebilirsiniz.	Kısaltıcı mekanizmasının bir boyutlu hücresel hareketlilerde gerçek zamanda simülasyonu / The Simulation of shrinkers by one dimensional cellular automata in real time Yazar:ZEKİ Danışman: PROF. DR. DOĞAN ÇALIKOĞLU Yer Bilgisi: GAZİ ÜNİVERSİTESİ / FEN BİLİMLERİ ENSTİTÜSÜ / ELEKTRONİK VE BİLGİSAYAR EĞİTİMİ ANABİLİM DALI Konu:Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control Anahtar Kelime:Kısaltıcı = Shrinker ; Zincir = Chain	Onaylandı Doktora Türkçe 2002 72 s.
KISALTICI MEKANİZMASININ BİR BOYUTLU HÜCRESEL HAREKETLİLERDE GERÇEK ZAMANDA SİMULASYONU (Doktora Tezi) Zeki ÇİFTÇİ GAZİ ÜNİVERSİTESİ FEN BİLİMLERİ ENSTİTÜSÜ Ocak 2002 ÖZET Girdi şeridi üzerinde, kısaltım işlemleri yaparak girdiyi tanıyan ve "kısaltıcı" olarak adlandırılan mekanizmalar vardır. Bu çalışmada önce, zincir adı verilen bir-boyutlu hücresel hareketlilerin belirlenimli kısaltıcıları gerçek zamanda simule edebildiği ortaya konmuştur. Zincirler, sonlu durumlu Moore makinelerinden oluşan bir-boyutlu hücresel yapılardır. Zincirde her hücrenin girişi, her iki yanındaki komşularının çıkışlarına bağlıdır. Burada, verilen herhangi bir belirlenimli kısaltıcıya karşılık, onu simule eden bir zincir olduğu gösterilirken, yapımsal ispat yöntemi kullanılmıştır. Kısaltıcı mekanizmasından hareketle kurulan zincir, aralarında başka simgeler olan dengeli parantezleri ve ortası belli palindromları kabul etmektedir. Zincir, bu dizgileri kabul ederken kısaltıcıya göre daha az sayıda geçiş yapmaktadır. Bu tez kapsamında elde edilen diğer bir önemli sonuç ta zincirlerin bir alt sınıfı olan Çok Gevşek (ÇG) bağlı zincirlerin, belirlenimsiz 1-dönüşlü kısaltıcı dillerini gerçek zamanda kabul ettiğidir. Kısaltıcıların bir alt sınıfı olan ve doğrusal dilleri tam olarak kabul eden 1-dönüşlü kısaltıcıların çalışması iki fazdan oluşmaktadır. Birinci fazda kafa, şerit üzerinde sabit bir yere konumlanır. İkinci fazda ise, sadece kısaltım işlemi yapılır. ÇG- zincirlerde bilgi akışı soldan sağa doğru tek bir yöndedir. Belirlenimsiz 1-dönüşlü kısaltıcının kabul ettiği palindromları ÇG-zincirlerin gerçek zamanda nasıl kabul ettiği gösterilmiştir. Bilim Kodu : 600.10.14 Anahtar Kelimeler: Zincir, kısaltıcı, 1-dönüşlü kısaltıcı, çok gevşek bağlı zincir, bir-boyutlu hücresel hareketli, yığmalı hareketli, doğrusal diller. Sayfa Adedi : 61 Tez Yöneticisi : Prof. Dr. Doğan ÇAUKOĞLU
m THE SIMULATION OF SHRINKERS BY ONE DIMENSIONAL CELLULAR AUTOMATA IN REAL TIME (Ph.D. Thesis) Zeki ÇİFTÇİ GAZI UNIVERSITY INSTITUTE OF SCIENCE AND TECHNOLOGY January 2002 ABSTRACT There are some mechanisms called shrinkers which recognize the input by performing shrinking operations on the input tape. In this work, first it is shown that one-dimensional cellular automata called chains can simulate deterministic shrinkers in real-time. Chains are one-dimensional cellular structures consisting of finite-state Moore machines. In a chain the input of each cell is connected to the outputs of the two neighboring cells on each side. Here a constructive proof method is employed in showing that a chain exists corresponding to any given deterministic shrinker which simulates it. The chain which is constructed corresponding to a shrinker can accept balanced parenthesis with embedded symbols and palindromes with distinguished centers. In accepting these strings a chain performs less number of transitions with respect to shrinkers. Another important result obtained in this thesis is that very weakly connected chains which are a subclass of chains can accept non-deterministic one-turn shrinker languages in real-time. The operation of one-turn shrinkers which constitute a subclass of shrinkers and which characterize linear languages consist of two phases. In the first phase, the head gets positioned at a fixed point on the tape. In the second phase, solely performs T.G. MSEKtitiBtnifi «u..*uj NRyMAHTASYOM UERfEZkIV shrinking operation. In very weakly connected chains the information flow is one way from left to right. It is demonstrated how very weakly connected chains accept the palindromes accepted by non-deterministic one-turn shrinkers in real-time. Science Code: 600.10.14 Key Words : Chain, shrinker, one-turn sh tinker, VW-chain, one- dimensional cellular automata, pushdown automata, linear language. Page Number : 61 Adviser : Prof. Dr. Doğan ÇALIKO?LU