| JIRÁSKOVÁ, Galina a Ondřej KLÍMA. Descriptional Complexity of Biautomata. In Martin Kutrib, Nelma Moreira, Rogério Reis. Descriptional Complexity of Formal Systems. Berlin Heidelberg: Springer-Verlag Berlin Heidelberg, 2012, s. 196-208. ISBN 978-3-642-31622-7. Dostupné z: https://dx.doi.org/10.1007/978-3-642-31623-4_15. |
Další formáty:
BibTeX
LaTeX
RIS
@inproceedings{991108,
author = {Jirásková, Galina and Klíma, Ondřej},
address = {Berlin Heidelberg},
booktitle = {Descriptional Complexity of Formal Systems},
doi = {http://dx.doi.org/10.1007/978-3-642-31623-4_15},
editor = {Martin Kutrib, Nelma Moreira, Rogério Reis},
keywords = {biautomata; descriptional complexity; minimal automaton},
howpublished = {tištěná verze "print"},
language = {eng},
location = {Berlin Heidelberg},
isbn = {978-3-642-31622-7},
pages = {196-208},
publisher = {Springer-Verlag Berlin Heidelberg},
title = {Descriptional Complexity of Biautomata},
year = {2012}
}
TY - JOUR
ID - 991108
AU - Jirásková, Galina - Klíma, Ondřej
PY - 2012
TI - Descriptional Complexity of Biautomata
PB - Springer-Verlag Berlin Heidelberg
CY - Berlin Heidelberg
SN - 9783642316227
KW - biautomata
KW - descriptional complexity
KW - minimal automaton
N2 - A biautomaton is a finite automaton which arbitrarily alternates between reading the input word from the left and from the right. Some compatibility assumptions in the formal definition of a biautomaton ensure that the acceptance of an input does not depend on the way how the input is read. The paper studies the constructions of biautomata from the descriptional point of view. It proves the tight bounds on the size of a biautomaton recognizing a regular language represented by a deterministic or nondeterministic automaton.
ER -
JIRÁSKOVÁ, Galina a Ondřej KLÍMA. Descriptional Complexity of Biautomata. In Martin Kutrib, Nelma Moreira, Rogério Reis. \textit{Descriptional Complexity of Formal Systems}. Berlin Heidelberg: Springer-Verlag Berlin Heidelberg, 2012, s.~196-208. ISBN~978-3-642-31622-7. Dostupné z: https://dx.doi.org/10.1007/978-3-642-31623-4\_{}15.
|
