All a b c d e f g h i j k l m n o p q r s t u v w x y z Other

Page 1

Displaying 1 – 3 of 3

Showing per page

Note on the complexity of Las Vegas automata problems

Galina Jirásková (2006)

RAIRO - Theoretical Informatics and Applications

We investigate the complexity of several problems concerning Las Vegas finite automata. Our results are as follows. (1) The membership problem for Las Vegas finite automata is in NL. (2) The nonemptiness and inequivalence problems for Las Vegas finite automata are NL-complete. (3) Constructing for a given Las Vegas finite automaton a minimum state deterministic finite automaton is in NP. These results provide partial answers to some open problems posed by Hromkovič and Schnitger [Theoret....

Note: The Smallest Nonevasive Graph Property

Michał Adamaszek (2014)

Discussiones Mathematicae Graph Theory

A property of n-vertex graphs is called evasive if every algorithm testing this property by asking questions of the form “is there an edge between vertices u and v” requires, in the worst case, to ask about all pairs of vertices. Most “natural” graph properties are either evasive or conjectured to be such, and of the few examples of nontrivial nonevasive properties scattered in the literature the smallest one has n = 6. We exhibit a nontrivial, nonevasive property of 5-vertex graphs and show that...

Currently displaying 1 – 3 of 3

Page 1