6 citations · 6 across the 4 of their papers we have counts for
3 papers · 1 filter
NL Is Strictly Contained in P
Santiago Flum, J. Andres Montoya
We prove that NL is strictly contained in P. We get this separation as a corollary of the following result: the set of context-free languages is not contained in NL. The reader sho…
On the synchronization of planar automata
J. Andres Montoya, Christian Nolasco
Planar automata seems to be representative of the synchronizing behavior of deterministic finite state automata. We conjecture that Černy's conjecture holds true, if and only if, i…
Can one quantum bit separate any pair of words with zero-error?
Aleksandrs Belovs, Juan Andres Montoya, Abuzer Yakaryılmaz
Determining the minimum number of states required by a finite automaton to separate a given pair of different words is an important problem. In this paper, we consider this problem…