• Find People
  • Campus Map
  • PiratePort
  • A-Z
    • About
    • Submit
    • Browse
    • Login
    View Item 
    •   ScholarShip Home
    • Academic Affairs
    • College of Engineering and Technology
    • Computer Science
    • View Item
    •   ScholarShip Home
    • Academic Affairs
    • College of Engineering and Technology
    • Computer Science
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    Browse

    All of The ScholarShipCommunities & CollectionsDateAuthorsTitlesSubjectsTypeDate SubmittedThis CollectionDateAuthorsTitlesSubjectsTypeDate Submitted

    My Account

    Login

    Statistics

    View Google Analytics Statistics

    Synchronizing Automata and the Černý Conjecture

    Thumbnail
    View/ Open
    Masters_ecu_0600M_10781.pdf (481.3Kb)

    Show full item record
    Author
    Masters, Miciah Dashiel Butler
    Abstract
    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.
    URI
    http://hdl.handle.net/10342/3937
    Subject
     Computer science; Automata; Černý conjecture; Deterministic; Finite-state; Synchronizing automata 
    Date
    2012
    Citation:
    APA:
    Masters, Miciah Dashiel Butler. (January 2012). Synchronizing Automata and the Černý Conjecture (Master's Thesis, East Carolina University). Retrieved from the Scholarship. (http://hdl.handle.net/10342/3937.)

    Display/Hide MLA, Chicago and APA citation formats.

    MLA:
    Masters, Miciah Dashiel Butler. Synchronizing Automata and the Černý Conjecture. Master's Thesis. East Carolina University, January 2012. The Scholarship. http://hdl.handle.net/10342/3937. March 04, 2021.
    Chicago:
    Masters, Miciah Dashiel Butler, “Synchronizing Automata and the Černý Conjecture” (Master's Thesis., East Carolina University, January 2012).
    AMA:
    Masters, Miciah Dashiel Butler. Synchronizing Automata and the Černý Conjecture [Master's Thesis]. Greenville, NC: East Carolina University; January 2012.
    Collections
    • Computer Science
    • Master's Theses
    Publisher
    East Carolina University

    xmlui.ArtifactBrowser.ItemViewer.elsevier_entitlement

    East Carolina University has created ScholarShip, a digital archive for the scholarly output of the ECU community.

    • About
    • Contact Us
    • Send Feedback