Completely Reachable Automata

Eugenija A. Bondar; Mikhail V. Volkov

doi:10.1007/978-3-319-41114-9_1

Conference Papers Year : 2016

Completely Reachable Automata

(1) , (1)

Eugenija A. Bondar

Function : Author
PersonId : 1022725

Ural Federal University [Ekaterinburg]

Mikhail V. Volkov

Function : Author

Ural Federal University [Ekaterinburg]

Abstract

We present a few results and several open problems concerning complete deterministic finite automata in which every non-empty subset of the state set occurs as the image of the whole state set under the action of a suitable input word.

Keywords

Deterministic finite automaton Complete reachability Transition monoid Syntactic complexity PSPACE-completeness

Domains

Computer Science [cs]

Fichier principal

416473_1_En_1_Chapter.pdf (187.88 Ko)

Origin : Files produced by the author(s)

Hal Ifip : Connect in order to contact the contributor

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

Submitted on : Monday, November 13, 2017-3:32:32 PM

Last modification on : Monday, November 13, 2017-3:35:36 PM

Long-term archiving on: Wednesday, February 14, 2018-3:13:24 PM

Dates and versions

hal-01633948 , version 1 (13-11-2017)

Licence

Attribution

Identifiers

HAL Id : hal-01633948 , version 1
DOI : 10.1007/978-3-319-41114-9_1

Cite

Eugenija A. Bondar, Mikhail V. Volkov. Completely Reachable Automata. 18th International Workshop on Descriptional Complexity of Formal Systems (DCFS), Jul 2016, Bucharest, Romania. pp.1-17, ⟨10.1007/978-3-319-41114-9_1⟩. ⟨hal-01633948⟩

Export

BibTeX XML-TEI Dublin Core DC Terms EndNote DataCite

Collections

IFIP-LNCS IFIP IFIP-TC IFIP-TC1 IFIP-WG IFIP-DCFS IFIP-LNCS-9777 IFIP-WG1-2

41 View

173 Download

Completely Reachable Automata

Abstract

Keywords

Domains

Dates and versions

Licence

Identifiers

Cite

Export

Collections

Altmetric

Share