Skip to Main content Skip to Navigation
Conference papers

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.
Document type :
Conference papers
Complete list of metadata

Cited literature [22 references]  Display  Hide  Download

https://hal.inria.fr/hal-01556220
Contributor : Hal Ifip <>
Submitted on : Tuesday, July 4, 2017 - 5:45:42 PM
Last modification on : Wednesday, November 18, 2020 - 7:20:08 PM
Long-term archiving on: : Friday, December 15, 2017 - 1:34:25 AM

File

978-3-642-33475-7_12_Chapter.p...
Files produced by the author(s)

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

Citation

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⟩

Share

Metrics

Record views

133

Files downloads

213