Skip to Main content Skip to Navigation
Conference papers

Reset Complexity of Ideal Languages Over a Binary Alphabet

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.
Document type :
Conference papers
Complete list of metadata

https://hal.inria.fr/hal-01656997
Contributor : Hal Ifip <>
Submitted on : Wednesday, December 6, 2017 - 11:43:35 AM
Last modification on : Wednesday, December 6, 2017 - 1:46:23 PM

File

440206_1_En_21_Chapter.pdf
Files produced by the author(s)

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

Citation

Marina Maslennikova. Reset Complexity of Ideal Languages Over a Binary Alphabet. 19th International Conference on Descriptional Complexity of Formal Systems (DCFS), Jul 2017, Milano, Italy. pp.262-273, ⟨10.1007/978-3-319-60252-3_21⟩. ⟨hal-01656997⟩

Share

Metrics

Record views

115

Files downloads

61