An FPGA based approach for Černý conjecture falsification

Warning The system is temporarily closed to updates for reporting purpose.

Koca, Çağla (2018) An FPGA based approach for Černý conjecture falsification. [Thesis]

PDF - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader

Official URL: http://risc01.sabanciuniv.edu/record=b1817047 (Table of Contents)


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 iii 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.

Item Type:Thesis
Uncontrolled Keywords:FPGA. -- Synchronizing sequences. -- Černý conjecture. -- APKD. -- Sıfırlama dizileri. -- Černý sanıtı.
Subjects:T Technology > TK Electrical engineering. Electronics Nuclear engineering > TK7800-8360 Electronics > TK7885-7895 Computer engineering. Computer hardware
ID Code:36581
Deposited By:IC-Cataloging
Deposited On:01 Oct 2018 13:12
Last Modified:25 Mar 2019 17:29

Repository Staff Only: item control page