On Properties and State Complexity of Deterministic State-Partition Automata

Abstract : A deterministic automaton accepting a regular language L is a state-partition automaton with respect to a projection P if the state set of the deterministic automaton accepting the projected language P(L), obtained by the standard subset construction, forms a partition of the state set of the automaton. In this paper, we study fundamental properties of state-partition automata. We provide a construction of the minimal state-partition automaton for a regular language and a projection, discuss closure properties of state-partition automata under the standard constructions of deterministic automata for regular operations, and show that almost all of them fail to preserve the property of being a state-partition automaton. Finally, we define the notion of a state-partition complexity, and prove the tight bound on the state-partition complexity of regular languages represented by incomplete deterministic automata.
Type de document :
Communication dans un congrès
Jos C. M. Baeten; Tom Ball; Frank S. Boer. 7th International Conference on Theoretical Computer Science (TCS), Sep 2012, Amsterdam, Netherlands. Springer, Lecture Notes in Computer Science, LNCS-7604, pp.164-178, 2012, Theoretical Computer Science. 〈10.1007/978-3-642-33475-7_12〉
Liste complète des métadonnées

Littérature citée [25 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01556220
Contributeur : Hal Ifip <>
Soumis le : mardi 4 juillet 2017 - 17:45:42
Dernière modification le : lundi 23 avril 2018 - 09:58:11
Document(s) archivé(s) le : vendredi 15 décembre 2017 - 01:34:25

Fichier

978-3-642-33475-7_12_Chapter.p...
Fichiers produits par l'(les) auteur(s)

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Citation

Galina Jirásková, Tomáš Masopust. On Properties and State Complexity of Deterministic State-Partition Automata. Jos C. M. Baeten; Tom Ball; Frank S. Boer. 7th International Conference on Theoretical Computer Science (TCS), Sep 2012, Amsterdam, Netherlands. Springer, Lecture Notes in Computer Science, LNCS-7604, pp.164-178, 2012, Theoretical Computer Science. 〈10.1007/978-3-642-33475-7_12〉. 〈hal-01556220〉

Partager

Métriques

Consultations de la notice

40

Téléchargements de fichiers

14