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.
|