6 citations · 6 across the 4 of their papers we have counts for
5 papers
The smallest programmable machine and the hardness of analyzing it
J. Andres Montoya
We investigate the computational complexity of analyzing the structural and behavioral properties of deterministic k-pebble automata, which represent a natural framework for studyi…
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…
The almost-entropic regions are not semialgebraic
Carolina Mejia, J. Andres Montoya
We prove that the almost-entropic region of order four is not semialgebraic, we get as a corollary the well-known Theorem of Matus, which asserts that this region is not polyhedral