P(L)AYING FOR SYNCHRONIZATION / Fominykh F. M.,Martyugin P. V.,Volkov M. V. // INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE. - 2013. - V. 24, l. 6, SI. - P. 765-780.

ISSN/EISSN:

0129-0541 / 1793-6373

Type:

Article

Abstract:

Two topics are presented: synchronization games and synchronization costs. In a synchronization game on a deterministic finite automaton, there are two players, Alice and Bob, whose moves alternate. Alice wants to synchronize the given automaton, while Bob aims to make her task as hard as possible. We answer a few natural questions related to such games. Speaking about synchronization costs, we consider deterministic automata in which each transition has a certain price. The problem is whether or not a given automaton can be synchronized within a given budget. We determine the complexity of this problem.

Author keywords:

Deterministic finite automaton; synchronizing automaton; synchronization game; deterministic weighted automaton; computational complexity AUTOMATA; SEQUENCES

DOI:

10.1142/S0129054113400170

Web of Science ID:

ISI:000329121500006

Соавторы в МНС:

Другие поля

Поле	Значение
Month	SEP
Publisher	WORLD SCIENTIFIC PUBL CO PTE LTD
Address	5 TOH TUCK LINK, SINGAPORE 596224, SINGAPORE
Language	English
EISSN	1793-6373
Keywords-Plus	AUTOMATA; SEQUENCES
Research-Areas	Computer Science
Web-of-Science-Categories	Computer Science, Theory \& Methods
Author-Email	FedorFo@yandex.ru martuginp@gmail.com Mikhail.Volkov@usu.ru
ResearcherID-Numbers	Volkov, Mikhail/F-1407-2014
ORCID-Numbers	Volkov, Mikhail/0000-0002-9327-243X
Funding-Acknowledgement	Russian Foundation for Basic Research {[}13-01-00852]; Presidential Program for young researchers {[}MK-266.2012.1]
Funding-Text	Supported by the Russian Foundation for Basic Research, grant 13-01-00852, and by the Presidential Program for young researchers, grant MK-266.2012.1.
Number-of-Cited-References	17
Usage-Count-Last-180-days	3
Usage-Count-Since-2013	22
Journal-ISO	Int. J. Found. Comput. Sci.
Doc-Delivery-Number	281SO