On Properties and State Complexity of Deterministic State-Partition Automata

JIRÁSKOVÁ, Galina and Tomáš MASOPUST. On Properties and State Complexity of Deterministic State-Partition Automata. In J.C.M. Baeten, T. Ball, and F.S. de Boer. IFIP Theoretical Computer Science 2012. Berlin, 2012, p. 164-178. ISBN 978-3-642-33474-0. Available from: https://doi.org/10.1007/978-3-642-33475-7_12.

Basic information

Original name

On Properties and State Complexity of Deterministic State-Partition Automata

Authors

JIRÁSKOVÁ, Galina and Tomáš MASOPUST

Edition

Berlin, IFIP Theoretical Computer Science 2012, p. 164-178, 2012

---

Other information

Type of outcome

Proceedings paper

Confidentiality degree

is not subject to a state or trade secret

Impact factor

Impact factor: 0.402 in 2005

ISBN

978-3-642-33474-0

ISSN

DOI

https://doi.org/10.1007/978-3-642-33475-7_12

Tags

International impact, Reviewed

---

Abstract

In the original language

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.