| Автор | Héam, Pierre-Cyrille |
| Дата выпуска | 2000 |
| dc.description | A reversible automaton is a finite automaton in which each letter induces a partial one-to-one map from the set of states into itself. We solve the following problem proposed by Pin. Given an alphabet A, does there exist a sequence of languages K <sub> n </sub> on A which can be accepted by a reversible automaton, and such that the number of states of the minimal automaton of K <sub> n </sub> is in O(n), while the minimal number of states of a reversible automaton accepting K <sub> n </sub> is in O(ρ <sup> n </sup>) for some ρ > 1? We give such an example with $\rho=\left(\frac{9}{8}\right)^{\frac{1}{12}}$. |
| Формат | application.pdf |
| Издатель | EDP Sciences |
| Копирайт | © EDP Sciences, 2000 |
| Тема | Automata |
| Тема | formal languages |
| Тема | reversible automata |
| Название | A Lower Bound For Reversible Automata |
| Тип | research-article |
| DOI | 10.1051/ita:2000120 |
| Electronic ISSN | 1290-385X |
| Print ISSN | 0988-3754 |
| Журнал | RAIRO - Theoretical Informatics and Applications |
| Том | 34 |
| Первая страница | 331 |
| Последняя страница | 341 |
| Аффилиация | Héam Pierre-Cyrille; LIAFA, Université Paris 7, 2 place Jussieu, 75251 Paris Cedex 05, France; (heam@liafa.jussieu.fr) |
| Выпуск | 5 |
