Reset complexity of ideal languages over a binary alphabet

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

Title:	Reset complexity of ideal languages over a binary alphabet
Authors:	Maslennikova, M.
Issue Date:	2017
Publisher:	Springer Verlag
Citation:	Maslennikova M. Reset complexity of ideal languages over a binary alphabet / M. Maslennikova. — DOI 10.1007/978-3-319-60252-3_21 // Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). — 2017. — Vol. 10316 LNCS. — P. 262-273.
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. © IFIP International Federation for Information Processing 2017.
Keywords:	IDEAL LANGUAGE PSPACE-COMPLETENESS RESET COMPLEXITY RESET WORD SYNCHRONIZING AUTOMATON DISPERSION COMPENSATION IDEAL LANGUAGE PSPACE COMPLETENESS RESET COMPLEXITY RESET WORDS SYNCHRONIZING AUTOMATA BINS
URI:	http://elar.urfu.ru/handle/10995/102109
Access:	info:eu-repo/semantics/openAccess
SCOPUS ID:	85022324516
WOS ID:	000440468100021
PURE ID:	83975bd9-d48a-4f69-9881-f144ddec6299 1977936
ISSN:	3029743
ISBN:	9783319602516
DOI:	10.1007/978-3-319-60252-3_21
Appears in Collections:	Научные публикации ученых УрФУ, проиндексированные в SCOPUS и WoS CC

Files in This Item:

File	Description	Size	Format
2-s2.0-85022324516.pdf		524,55 kB	Adobe PDF	View/Open