Další formáty:
BibTeX
LaTeX
RIS
@inproceedings{986799,
author = {Jirásková, Galina and Masopust, Tomáš},
address = {Berlin},
booktitle = {IFIP Theoretical Computer Science 2012},
doi = {http://dx.doi.org/10.1007/978-3-642-33475-7_12},
editor = {J.C.M. Baeten, T. Ball, and F.S. de Boer},
location = {Berlin},
isbn = {978-3-642-33474-0},
pages = {164-178},
title = {On Properties and State Complexity of Deterministic State-Partition Automata},
year = {2012}
}
TY - JOUR
ID - 986799
AU - Jirásková, Galina - Masopust, Tomáš
PY - 2012
TI - On Properties and State Complexity of Deterministic State-Partition Automata
CY - Berlin
SN - 9783642334740
N2 - 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.
ER -
JIRÁSKOVÁ, Galina a Tomáš MASOPUST. On Properties and State Complexity of Deterministic State-Partition Automata. In J.C.M. Baeten, T. Ball, and F.S. de Boer. \textit{IFIP Theoretical Computer Science 2012}. Berlin, 2012, s.~164-178. ISBN~978-3-642-33474-0. Dostupné z: https://dx.doi.org/10.1007/978-3-642-33475-7\_{}12.
|
