On Properties and State Complexity of Deterministic State-Partition Automata

Galina JiráskováGalina Jirásková, Tomáš MasopustTomáš Masopust

ISBN: 978-3-642-33474-0
Download
DOI Link

Galina Jirásková, Tomáš Masopust
On Properties and State Complexity of Deterministic State-Partition Automata
In J. C. M. Baeten, T. Ball, F. S. de Boer, eds., Proc. of 7th International Conference on Theoretical Computer Science (IFIP TCS), volume 7604 of LNCS, 164-178, 2012. Springer

Details
Bibtex

KurzfassungAbstract
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.
Forschungsgruppe:Research Group: Wissensbasierte SystemeKnowledge-Based Systems

The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-642-33475-7_12.

@inproceedings{JM2012,
  author    = {Galina Jir{\'{a}}skov{\'{a}} and Tom{\'{a}}{\v{s}} Masopust},
  title     = {On Properties and State Complexity of Deterministic
               State-Partition Automata},
  editor    = {J. C. M. Baeten and T. Ball and F. S. de Boer},
  booktitle = {Proc. of 7th International Conference on Theoretical Computer
               Science (IFIP {TCS)}},
  series    = {LNCS},
  volume    = {7604},
  publisher = {Springer},
  year      = {2012},
  pages     = {164-178},
  doi       = {10.1007/978-3-642-33475-7_12}
}