Open AccessThe Length of Subset Reachability in Nondeterministic Automata
Author(s) -
Pavel Martyugin
Publication year - 2008
Publication title -
electronic notes in theoretical computer science
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.242
H-Index - 60
ISSN - 1571-0661
DOI - 10.1016/j.entcs.2008.12.039
Subject(s) - reachability , nondeterministic algorithm , nondeterministic finite automaton , discrete mathematics , automaton , mathematics , combinatorics , computer science , ω automaton , quantum finite automata , automata theory , reachability problem , theoretical computer science
We study subset reachability in nondeterministic finite automata and look for bounds of the length of the shortest reaching words for automata with a fixed number of states. We obtain such bounds for nondeterministic automata over 2-letter, 3-letter and arbitrary alphabets
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom