Home > Search Results: keywords:"Finite automata|Distinguishing words|Complexity|Random automata"
Search:
Search Tips :: Advanced Search
Search collections:
Sort by: Display results: Output format:
National Repository of Grey Literature 1 records found  Search took 0.01 seconds. 
Distinguishing pairs of words using finite automata
 Bilan, Daria ; Koucký, Michal (advisor) ; Šámal, Robert (referee)
This work considers a fundamental open problem in informatics - distin- guishing two words by a deterministic finite automaton with the smallest pos- sible number of states. We review the existing research, where proven lower and upper bounds in terms of words' lengths differ exponentially. Next, we empirically try two approaches not studied previously: analysis of discerning sets and application of randomly generated automata. We show that the first approach does not help improve the bounds for the main problem, while the random automata could be successful for randomly taken word pairs but not for all of them. A combination of a randomly generated automaton with the best performing already known, though, may decrease an average number of states by several orders of magnitude. We propose several topics for further investigation based on the obtained experimental results. 1
Detailed record

Interested in being notified about new results for this query?
Subscribe to the RSS feed.
Digital Repository :: Search :: Submit :: Personalize :: Help
Powered by Invenio v1.1.2
Maintained by admin.invenio@techlib.cz
This site is also available in the following languages:
Česky  English