Tools

LEADER 03278cam a2200481Ia 4500

001 ocn810198982;

003 OCoLC;

005 20141212032705.0;

006 m d ;

007 cr bn|||||||||;

008 120918s2012 ncu ob 000 0 eng d;

035 a| (Sirsi) o810198982;

035 a| (OCoLC)810198982;

049 a| EREE;

090 a| QA267;

100 1 a| Masters, Miciah Dashiel Butler.?| UNAUTHORIZED;

245 10 a| Synchronizing automata and the Černý Conjecture /c| Miciah Dashiel Butler Masters.;

260 a| [Greenville, N.C.] :b| East Carolina University,c| 2012.;

300 a| 96 pages :b| digital, PDF file;

336 a| text2| rdacontent;

337 a| computer2| rdamedia;

338 a| online resource2| rdacarrier;

538 a| System requirements: Adobe Reader.;

538 a| Mode of access: World Wide Web.;

502 b| M.S.c| East Carolina Universityd| 2012.;

500 a| Presented to the faculty of the Department of Computer Science.;

500 a| Advisor: Krishnan Gopalakrishnan.;

500 a| Title from PDF t.p. (viewed Oct. 11, 2012).;

520 3 a| We provide a survey of research surrounding the Černý conjecture. This conjecture concerns finite-state automata that have the property of being "synchronizing." A synchronizing automaton is one for which there exists some input sequence that causes the automaton to transition to some fixed state, irrespective of the state in which it had been before reading that input sequence. The Černý conjecture states that, if an automaton with n states is synchronizing, then there exists some input sequence of length at most (n - 1)² that synchronizes it. We first survey the basic results that deal with synchronization of finite-state automata. We also study and implement several related algorithms, including Eppstein's greedy algorithm for producing a reset sequence. An analysis of the length of the sequence produced by this algorithm leads to an interesting problem in extremal combinatorics, the solution of which yields an upper bound of (n³ - n)/6 on the length of the sequence. We then investigate a generalization of the Černý conjecture. Next, we study extremal automata, for which the length of the shortest synchronizing sequence meets the Černý bound. We then turn our attention to subclasses of automata for which the Černý conjecture has been proved. Finally, we discuss possible approaches and current efforts to proving the Černý conjecture, as well as some related problems from the literature.;

504 a| Includes bibliographical references.;

650 0 a| Machine theory.=| ^A16040;

650 0 a| Robotsx| Programming.=| ^A158910;

653 a| Computer science;

700 1 a| Gopalakrishnan, Krishnan.?| UNAUTHORIZED;

710 2 a| East Carolina University.b| Department of Computer Science.?| UNAUTHORIZED;

856 40 z| Access via ScholarShipu| http://hdl.handle.net/10342/3937;

949 o| jgml;

994 a| C0b| ERE;

596 a| 1 4;

998 a| 3108499;

999 a| CLICK ON WEB ADDRESSw| ASISc| 1i| 3108499-1001l| JNETm| JOYNERr| Ys| Yt| JNE3ETDu| 9/18/2012x| ETDz| JERESOURCE;

999 a| CLICK ON WEB ADDRESSw| ASISc| 1i| 3108499-2001l| HSLELECm| HSLr| Ys| Yt| HEETDu| 9/18/2012x| ETDz| HERESOURCE;

Synchronizing automata and the Černý Conjecture / Miciah Dashiel Butler Masters.

Author/creator	Masters, Miciah Dashiel Butler
Other author	Gopalakrishnan, Krishnan.
Other author	East Carolina University. Department of Computer Science.
Format	Theses and dissertations
Publication Info	[Greenville, N.C.] : East Carolina University, 2012.
Description	96 pages : digital, PDF file
Supplemental Content	Access via ScholarShip
Subjects	Machine theory. Robots--Programming.

Summary	We provide a survey of research surrounding the Černý conjecture. This conjecture concerns finite-state automata that have the property of being "synchronizing." A synchronizing automaton is one for which there exists some input sequence that causes the automaton to transition to some fixed state, irrespective of the state in which it had been before reading that input sequence. The Černý conjecture states that, if an automaton with n states is synchronizing, then there exists some input sequence of length at most (n - 1)² that synchronizes it. We first survey the basic results that deal with synchronization of finite-state automata. We also study and implement several related algorithms, including Eppstein's greedy algorithm for producing a reset sequence. An analysis of the length of the sequence produced by this algorithm leads to an interesting problem in extremal combinatorics, the solution of which yields an upper bound of (n³ - n)/6 on the length of the sequence. We then investigate a generalization of the Černý conjecture. Next, we study extremal automata, for which the length of the shortest synchronizing sequence meets the Černý bound. We then turn our attention to subclasses of automata for which the Černý conjecture has been proved. Finally, we discuss possible approaches and current efforts to proving the Černý conjecture, as well as some related problems from the literature.
General note	Presented to the faculty of the Department of Computer Science.
General note	Advisor: Krishnan Gopalakrishnan.
General note	Title from PDF t.p. (viewed Oct. 11, 2012).
Dissertation note	M.S. East Carolina University 2012.
Bibliography note	Includes bibliographical references.
Technical details	System requirements: Adobe Reader.
Technical details	Mode of access: World Wide Web.

Synchronizing automata and the Černý Conjecture / Miciah Dashiel Butler Masters.

Click here for more information about this title