Inproceedings3006: Unterschied zwischen den Versionen
Aus International Center for Computational Logic
Markus Krötzsch (Diskussion | Beiträge) K (Textersetzung - „}} {{Publikation Author |Rank=2 |Author=“ durch „|FurtherAuthors=“) |
Tomas Masopust (Diskussion | Beiträge) Keine Bearbeitungszusammenfassung |
||
| Zeile 1: | Zeile 1: | ||
{{Publikation Erster Autor | {{Publikation Erster Autor | ||
|ErsterAutorVorname=Galina | |||
|ErsterAutorNachname=Jirásková | |ErsterAutorNachname=Jirásková | ||
|FurtherAuthors=Tomáš Masopust | |FurtherAuthors=Tomáš Masopust | ||
}} | }} | ||
| Zeile 19: | Zeile 19: | ||
|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. | |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. | ||
|ISBN=978-3-642-33474-0 | |ISBN=978-3-642-33474-0 | ||
|Download=On Properties and State Complexity of Deterministic State-Partition Automata.pdf | |||
|DOI Name=10.1007/978-3-642-33475-7_12 | |DOI Name=10.1007/978-3-642-33475-7_12 | ||
|Forschungsgruppe=Knowledge Systems | |Forschungsgruppe=Knowledge Systems | ||
}} | }} | ||
Version vom 29. Oktober 2014, 16:16 Uhr
On Properties and State Complexity of Deterministic State-Partition Automata
Galina JiráskováGalina Jirásková, Tomáš MasopustTomáš Masopust
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
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
- 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: Knowledge SystemsKnowledge-Based Systems
@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}
}
