Tytuł artykułu
Wybrane pełne teksty z tego czasopisma
Identyfikatory
Warianty tytułu
Języki publikacji
Abstrakty
We investigate and compare the descriptional power of unary probabilistic and nondeterministic automata (pfa's and nfa's, respectively). We show the existence of a family of languages hard for pfa’s in the following sense: For any positive integer d, there exists a unary d-cyclic language such that any pfa accepting it requires d states, as the smallest deterministic automaton. On the other hand, we prove that there exist infinitely many languages having pfa’s which from one side do not match a known optimal state lower bound and, on the other side, they are smaller than nfa’s which, in turn, are smaller than deterministic automata.
Wydawca
Czasopismo
Rocznik
Tom
Strony
119--135
Opis fizyczny
Bibliogr. 12 poz.
Twórcy
autor
autor
autor
autor
- Dipartimento di Scienze dell’Informazione, Universita degli Studi di Milano, via Comelico 39, 20135 Milano, Italy, mereghetti@dsi.unimi.it
Bibliografia
- [1] Ambainis, A.: The complexity of probabilistic versus deterministic finite automata, Proc. Algorithms and Computation, LNCS 1178, Springer, Berlin 1996, 233-238,
- [2] Chrobak, M.: Finite automata and unary languages, Theoretical Computer Science, 47, 1986, 149-158. Erratum, Ibid., 302, 2003, 497-498.
- [3] Isaacson, D.L., Madsen R.W.: Markov Chains Theory and Applications, J. Wiley & Sons, Inc., 1976.
- [4] Jiang,T.,McDowell, E., Ravikumar, B.: The structure and complexity of minimal nfa's over a unary alphabet, Int. J. Found. Comp. Sc., 2, 1991, 163-182.
- [5] Mereghetti, C., Pighizzini, G.: Two-way automata simulations and unary languages, J. Automata, Languages and Combinatorics, 5, 2000, 287-300.
- [6] Mera, F., Pighizzini, G.: Complementing unary nondeterministic automata, Theoretical Computer Science, 330, 2005, 349-360.
- [7] Mereghetti, C., Palano, B., Pighizzini, G.: Note on the succinctness of deterministic, nondeterministic, probabilistic and quantum finite automata, Theor. Inf. Appl., 5, 2001, 477-490.
- [8] Milani, M., Pighizzini, G.: Tight bounds on the simulation of unary probabilistic automata by deterministic automata, J. Automata, Languages and Combinatorics, 6, 2001, 481-492.
- [9] Paz, A.: Introduction to Probabilistic Automata, Academic Press, New York, 1971.
- [10] Rabin, M.: Probabilistic automata, Information and Control, 6, 1963, 230-245.
- [11] Rabin, M., Scott, D.: Finite automata and their decision problems, IBM J. Res. Develop., 3, 1959, 114-125.
- [12] Seneta, E.: Non-negativeMatrices and Markov Chains - 2nd Ed., Springer-Verlag, Berlin, 1981
Typ dokumentu
Bibliografia
Identyfikator YADDA
bwmeta1.element.baztech-article-BUS8-0022-0052