Reset Complexity of Ideal Languages over a Binary Alphabet

Maslennikova, M.

doi:10.1142/S0129054119400343

Please use this identifier to cite or link to this item: http://elar.urfu.ru/handle/10995/89984

Title:	Reset Complexity of Ideal Languages over a Binary Alphabet
Authors:	Maslennikova, M.
Issue Date:	2019
Publisher:	World Scientific Publishing Co. Pte Ltd
Citation:	Maslennikova, M. Reset Complexity of Ideal Languages over a Binary Alphabet / M. Maslennikova. — DOI 10.1142/S0129054119400343 // International Journal of Foundations of Computer Science. — 2019. — Vol. 6-7. — Iss. 30. — P. 1177-1196.
Abstract:	We prove PSPACE-completeness of checking whether a given ideal language serves as the language of reset words for some automaton with at most four states over a binary alphabet. We compare the reset complexity and the state complexity for languages related to slowly synchronizing automata. © 2019 World Scientific Publishing Company.
Keywords:	IDEAL LANGUAGE PSPACE-COMPLETENESS RESET COMPLEXITY RESET WORD STATE COMPLEXITY SYNCHRONIZING AUTOMATON
URI:	http://elar.urfu.ru/handle/10995/89984
Access:	info:eu-repo/semantics/openAccess
SCOPUS ID:	85072910392
WOS ID:	000486709700016
PURE ID:	10786749
ISSN:	0129-0541
DOI:	10.1142/S0129054119400343
Sponsorship:	Russian Foundation for Basic Research, RFBR: 16-01-00795 Ministry of Education and Science of the Russian Federation, Minobrnauka: 1.3253.2017 Ural Federal University, UrFU The author acknowledges anonymous reviewers for comments and suggestions. Also the author acknowledges support by the Russian Foundation for Basic Research, Grant No. 16-01-00795, the Ministry of Education and Science of the Russian Federation, Project No. 1.3253.2017, and the Competitiveness Enhancement Program of Ural Federal University.
Appears in Collections:	Научные публикации ученых УрФУ, проиндексированные в SCOPUS и WoS CC

Files in This Item:

File	Description	Size	Format
10.1142-S0129054119400343.pdf		524,55 kB	Adobe PDF	View/Open

Show full item record