Advanced search

Browse by subject

Browse by provider

Browse by language

Content Details
Normal View
CIP View

On two Algorithmic Problems about Synchr...

Berlinkov, Mikhail V...

Free

Share this content

On two Algorithmic Problems about Synchronizing Automata by Berlinkov, Mikhail V. ( Author )

Content Provider	Lemonjar Open Access
Publisher	Australian National University
Publication Date	01-09-2023
Summary	Under the assumption $\mathcal{P} \neq \mathcal{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 is, given an $n$-state binary complete synchronizing automaton, to compute its reset threshold within performance ratio less than $d \ln{(n)}$ for a specific constant $d>0$.
ISBN	-
Item Type	Article
File Type	pdf
File Size	29.34 KB
Language	English
Subjects	-
Unlimited	MYR 0.01
Total read	-
URL	http://arxiv.org/abs/1312.2226

Citation

Review the full bibliography data and make any necessary corrections before using. Always consult your library resources for the exact formatting and punctuation guidelines.

AMA 11th EditionReferences

Berlinkov, Mikhail V.. On two Algorithmic Problems about Synchronizing Automata. Australian National University. September 01, 2023. Accessed August 05, 2025. https://online.provdatabase.com/cite/22927

APA 7th EditionReferences

Berlinkov, Mikhail V.. (2023). On two Algorithmic Problems about Synchronizing Automata. Australian National University. https://online.provdatabase.com/cite/22927

Chicago 17th EditionReferences

Berlinkov, Mikhail V.. On two Algorithmic Problems about Synchronizing Automata. Australian National University. 2023. https://online.provdatabase.com/cite/22927

HarvardReferences

Berlinkov, Mikhail V.. (2023). On two Algorithmic Problems about Synchronizing Automata. [Online]. Australian National University. Available from: https://online.provdatabase.com/cite/22927. (Accessed 05 August 2025).

Harvard AustraliaReferences

Berlinkov, Mikhail V., 2023, On two Algorithmic Problems about Synchronizing Automata, Australian National University, viewed 05 August 2025, <https://online.provdatabase.com/cite/22927>

MLA 9th EditionWorks Cited

Berlinkov, Mikhail V.. On two Algorithmic Problems about Synchronizing Automata. Australian National University, 2023. PROV Database, https://online.provdatabase.com/cite/22927.

Share this eBook