Reset Complexity of Ideal Languages Over a Binary Alphabet - Descriptional Complexity of Formal Systems (DCFS 2017)
Conference Papers Year : 2017

Reset Complexity of Ideal Languages Over a Binary Alphabet

Marina Maslennikova
  • Function : Author
  • PersonId : 1024580
Ural Federal University [Ekaterinburg]

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.

Domains

Computer Science [cs]
Fichier principal
Vignette du fichier
440206_1_En_21_Chapter.pdf (153.26 Ko) Télécharger le fichier
Origin Files produced by the author(s)

Hal Ifip  : Connect in order to contact the contributor

https://inria.hal.science/hal-01656997

Submitted on : Wednesday, December 6, 2017-11:43:35 AM

Last modification on : Wednesday, December 6, 2017-1:46:23 PM

Download

Dates and versions

hal-01656997 , version 1 (06-12-2017)

Licence

Attribution

Identifiers

Cite

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⟩

Export

BibTeX XML-TEI Dublin Core DC Terms EndNote DataCite

Collections

IFIP-LNCS IFIP IFIP-TC IFIP-TC1 IFIP-WG IFIP-DCFS IFIP-WG1-2 IFIP-LNCS-10316
44 View
45 Download

Altmetric

Share

More