%0 Conference Proceedings
%T On Properties and State Complexity of Deterministic State-Partition Automata
%+ Slovak Academy of Sciences (SAS)
%+ Czech Academy of Sciences [Prague] (CAS)
%A Jirásková, Galina
%A Masopust, Tomáš
%< avec comité de lecture
%( Lecture Notes in Computer Science
%B 7th International Conference on Theoretical Computer Science (TCS)
%C Amsterdam, Netherlands
%Y Jos C. M. Baeten
%Y Tom Ball
%Y Frank S. Boer
%I Springer
%3 Theoretical Computer Science
%V LNCS-7604
%P 164-178
%8 2012-09-26
%D 2012
%R 10.1007/978-3-642-33475-7_12
%K Regular languages
%K finite automata
%K descriptional complexity
%K projections
%K state-partition automata
%Z Computer Science [cs]Conference papers
%X 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.
%G English
%Z TC 1
%Z TC 2
%Z WG 2.2
%2 https://inria.hal.science/hal-01556220/document
%2 https://inria.hal.science/hal-01556220/file/978-3-642-33475-7_12_Chapter.pdf
%L hal-01556220
%U https://inria.hal.science/hal-01556220
%~ IFIP-LNCS
%~ IFIP
%~ IFIP-TC
%~ IFIP-TC1
%~ IFIP-TC2
%~ IFIP-TCS
%~ IFIP-WG2-2
%~ IFIP-LNCS-7604