Zobrazeno 1 - 6
of 6
pro vyhledávání: '"Berlinkov M"'
Autor:
Berlinkov, M. V.
The well known open \v{C}ern\'y conjecture states that each \san with $n$ states has a \sw of length at most $(n-1)^2$. On the other hand, the best known upper bound is cubic of $n$. Recently, in the paper \cite{CARPI1} of Alessandro and Carpi, the a
Externí odkaz:
http://arxiv.org/abs/0909.3790
Autor:
Berlinkov, M. V.
We prove that, unless $\mathrm{P}=\mathrm{NP}$, no polynomial algorithm can approximate the minimum length of \sws for a given \san within a constant factor.
Comment: 12 pages, 1 figure
Comment: 12 pages, 1 figure
Externí odkaz:
http://arxiv.org/abs/0909.3787
Autor:
Berlinkov, M. V.
Publikováno v:
Lect. Notes Comput. Sci.
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Under the assumption P=NP, we prove that two natural problems from the theory of synchronizing automata cannot be solved in polynomial time. The first problem is to decide whether a given reachable partial automaton is synchronizing. The second one i
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=od_______917::a505a52365ff3fec8f946cc6b52c6c18
https://www.scopus.com/inward/record.uri?eid=2-s2.0-84958541625&doi=10.1007/978-3-319-09698-8_6&partnerID=40&md5=a867f501652a51f75cc027db0fc8e494
https://www.scopus.com/inward/record.uri?eid=2-s2.0-84958541625&doi=10.1007/978-3-319-09698-8_6&partnerID=40&md5=a867f501652a51f75cc027db0fc8e494
Publikováno v:
Int. J. Found. Comput. Sci.
International Journal of Foundations of Computer Science
International Journal of Foundations of Computer Science
Černý's conjecture asserts the existence of a synchronizing word of length at most (n - 1)2 for any synchronized n-state deterministic automaton. We prove a quadratic upper bound on the length of a synchronizing word for any synchronized n-state de
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=od_______917::9c922ceac1ee8f18ce766197253e1e23
https://hdl.handle.net/10995/111871
https://hdl.handle.net/10995/111871
Kniha
Tento výsledek nelze pro nepřihlášené uživatele zobrazit.
K zobrazení výsledku je třeba se přihlásit.
K zobrazení výsledku je třeba se přihlásit.
Akademický článek
Tento výsledek nelze pro nepřihlášené uživatele zobrazit.
K zobrazení výsledku je třeba se přihlásit.
K zobrazení výsledku je třeba se přihlásit.