An FPGA Based Approach for Černý Conjecture Falsification
Černý Sanıtı Yanlışlaması için APKD Tabanlı Yaklaşım
- Tez No: 507369
- Danışmanlar: PROF. DR. ERKAY SAVAŞ, DOÇ. DR. HÜSNÜ YENİGÜN
- Tez Türü: Yüksek Lisans
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2018
- Dil: İngilizce
- Üniversite: Sabancı Üniversitesi
- Enstitü: Mühendislik ve Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Belirtilmemiş.
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: Belirtilmemiş.
Özet
Bir sıfırlama dizisi, verilen bir özdevinimin tüm durumlarını aynı duruma getirmeye yarayan bir girdi dizisidir. J. Černý n durumlu bir özdevinim için en kısa sıfırlama dizisi boyunun (n-1)^2'den daha uzun olamayacağı varsayımında bulunmuştur. Bu varsayım günümüzde Černý sanıtı olarak adlandırılmaktadır. Bu yarım asırlık eski varsayım hala açıktır ve sonlu durum özdevinim kombinatoryal teorisinde en uzun süre çözülemeyen problem olarak kabul edilmektedir. Literatürde yürütülen çalışmalardan bir tanesi, n durum sayısına sahip tüm özdevinimleri ele alarak ve bu özdevinimlerin hepsinde sanıtın doğru olup olmadığı kontrol ederek, belli bir n durum sayısına sahip özdevimler için Černý sanıtının doğruluğunu kontrol etmektir. Bu, sadece 2 girdili ve durum sayısı 12 veya daha az olan tüm özdevinimler için bile hesaplama açısından yoğun bir işlemdir. Arama işlemlerini hızlandırmak için çok çekirdekli CPU'lar kullanan paralel hesaplama yöntemleri daha önce denenmiştir. Bu tezde, Černý sanıtını yanlışlayan bir özdevinim arayışını hızlandırmak için Alanda Programlanabilir Kapı Dizileri (APKD) kullanımı üzerine çalışılmaktadır. Sonlu bir durum özdevinimin en kısa sıfırlama dizisi boyunu hesaplayan bir tasarım sunulmaktadır. Önerilen tasarım, donanım tasarımlarının paralel hesaplama imkanlarıyla zaman performansını optimize ederek uygulanmaktadır.
Özet (Çeviri)
A synchronizing sequence for an automaton is a special input sequence that sends all states of the automaton to the same state. J. Černý conjectured that the length of the shortest synchronizing sequence of an automaton with n states cannot be greater than (n-1)^2, which is known today as the Černý conjecture. This half-a-century old conjecture is still open and it is considered to be the most long-standing open problem in the combinatorial theory of finite state automata. One research line that has been pursued in the literature is to check if the conjecture holds for a fixed number of states n, by considering all automata with n states and checking if any of these automata falsifies the conjecture. This is a computationally intensive task, even for automata up to a dozen of states and only two input symbols. To accelerate the search parallel computation approaches using multicore CPUs have been tried before. In this thesis, we study the use of FPGAs to accelerate the search for an automaton falsifying the Černý conjecture. We present a design to calculate the minimum length synchronizing sequence of a finite state automaton. The proposed design is implemented with the parallel computing capability of hardware designs while optimizing the time performance.
Benzer Tezler
- A systematic approach for register file design in FPGAs
Yazmaç dosyaları için sistematik tasarım yaklaşımı
HASAN ERDEM YANTIR
Yüksek Lisans
İngilizce
2014
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolBoğaziçi ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DOÇ. DR. ARDA YURDAKUL
- Mikroşebekelerde ada mod çalışmanın tespiti ve güç kalitesi olaylarının sınıflandırılması için yapay zekâ tabanlı kontrol yöntemlerinin geliştirilmesi
Development of artificial intelligence based control methods for detection of islanding conditions and classification of power quality events in microgrids
ALPER YILMAZ
Doktora
Türkçe
2023
Elektrik ve Elektronik MühendisliğiBursa Teknik ÜniversitesiElektrik-Elektronik Mühendisliği Ana Bilim Dalı
DOÇ. DR. GÖKAY BAYRAK
- FPGA based hardware accelerator for euler equations with finite volume method
Euler denklemleri için sonlu hacimler yöntemi ile FPGA tabanlı donanım hızlandırıcı
EMİNE ELİF YİĞİT
Yüksek Lisans
İngilizce
2024
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiSavunma Teknolojileri Ana Bilim Dalı
DR. ÖĞR. ÜYESİ RAMAZAN YENİÇERİ
- FPGA tabanlı çok fonksiyonlu ultrasonik temizleme makinesi tasarımı ve prototip üretimi
Design and prototype implementation of an FPGA based multi-functional ultrasonic cleaning machine
ULVİ GÜVENÇ
Yüksek Lisans
Türkçe
2011
Elektrik ve Elektronik MühendisliğiKocaeli ÜniversitesiElektronik ve Haberleşme Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. ALİ TANGEL
- Simulation of fpga-based image processing system for quality control and palletization applications
Kalıte kontrol ve paletleme uygulamaları ıçın fpga tabanlı görüntü ışleme sıstemı sımülasyonu
ABUBAKAR ASHİR
Yüksek Lisans
İngilizce
2014
Elektrik ve Elektronik MühendisliğiMevlana ÜniversitesiElektrik-Elektronik Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. MOHAMMAD SHUKRI SALMAN
PROF. DR. ATEF ABDELMONEIM ATA