On two algorithmic problems about synchronizing automata (Short Paper)

Berlinkov, M. V.

doi:10.1007/978-3-319-09698-8_6

Пожалуйста, используйте этот идентификатор, чтобы цитировать или ссылаться на этот ресурс: http://elar.urfu.ru/handle/10995/102294

Полная запись метаданных

Поле DC	Значение	Язык
dc.contributor.author	Berlinkov, M. V.	en
dc.date.accessioned	2021-08-31T15:03:00Z	-
dc.date.available	2021-08-31T15:03:00Z	-
dc.date.issued	2014	-
dc.identifier.citation	Berlinkov M. V. On two algorithmic problems about synchronizing automata (Short Paper) / M. V. Berlinkov. — DOI 10.1007/978-3-319-09698-8_6 // Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). — 2014. — Vol. 8633 LNCS. — P. 61-67.	en
dc.identifier.isbn	9783319096971	-
dc.identifier.issn	3029743	-
dc.identifier.other	Final	2
dc.identifier.other	All Open Access, Green	3
dc.identifier.other	https://www.scopus.com/inward/record.uri?eid=2-s2.0-84958541625&doi=10.1007%2f978-3-319-09698-8_6&partnerID=40&md5=a867f501652a51f75cc027db0fc8e494
dc.identifier.other	http://arxiv.org/pdf/1312.2226.pdf	m
dc.identifier.uri	http://elar.urfu.ru/handle/10995/102294	-
dc.description.abstract	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 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. © 2014 Springer International Publishing Switzerland.	en
dc.format.mimetype	application/pdf	en
dc.language.iso	en	en
dc.publisher	Springer Verlag	en
dc.rights	info:eu-repo/semantics/openAccess	en
dc.source	Lect. Notes Comput. Sci.	2
dc.source	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)	en
dc.subject	ALGORITHMS	en
dc.subject	POLYNOMIAL APPROXIMATION	en
dc.subject	ALGORITHMIC PROBLEMS	en
dc.subject	PARTIAL AUTOMATON	en
dc.subject	PERFORMANCE RATIO	en
dc.subject	POLYNOMIAL-TIME	en
dc.subject	SYNCHRONIZING AUTOMATA	en
dc.subject	AUTOMATA THEORY	en
dc.title	On two algorithmic problems about synchronizing automata (Short Paper)	en
dc.type	Conference Paper	en
dc.type	info:eu-repo/semantics/conferenceObject	en
dc.type	info:eu-repo/semantics/publishedVersion	en
dc.identifier.doi	10.1007/978-3-319-09698-8_6	-
dc.identifier.scopus	84958541625	-
local.contributor.employee	Berlinkov, M.V., Institute of Mathematics and Computer Science, Ural Federal University, 620000 Ekaterinburg, Russian Federation
local.description.firstpage	61	-
local.description.lastpage	67	-
local.volume	8633 LNCS	-
local.contributor.department	Institute of Mathematics and Computer Science, Ural Federal University, 620000 Ekaterinburg, Russian Federation
local.identifier.pure	367054	-
local.identifier.pure	3e49a695-6032-4799-a303-0f91cd3bd7c8	uuid
local.identifier.eid	2-s2.0-84958541625	-
Располагается в коллекциях:	Научные публикации ученых УрФУ, проиндексированные в SCOPUS и WoS CC

Файлы этого ресурса:

Файл	Описание	Размер	Формат
2-s2.0-84958541625.pdf		132,23 kB	Adobe PDF	Просмотреть/Открыть

Показать базовое описание ресурса Статистика

Все ресурсы в архиве электронных ресурсов защищены авторским правом, все права сохранены.