On Properties and State Complexity of Deterministic State-Partition Automata - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2012

On Properties and State Complexity of Deterministic State-Partition Automata

Galina Jirásková
  • Fonction : Auteur
  • PersonId : 1011781
Tomáš Masopust
  • Fonction : Auteur
  • PersonId : 1011793

Résumé

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.
Fichier principal
Vignette du fichier
978-3-642-33475-7_12_Chapter.pdf (335.83 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-01556220 , version 1 (04-07-2017)

Licence

Paternité

Identifiants

Citer

Galina Jirásková, Tomáš Masopust. On Properties and State Complexity of Deterministic State-Partition Automata. 7th International Conference on Theoretical Computer Science (TCS), Sep 2012, Amsterdam, Netherlands. pp.164-178, ⟨10.1007/978-3-642-33475-7_12⟩. ⟨hal-01556220⟩
62 Consultations
104 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More