On the Size of Unary Probabilistic and Nondeterministic Automata

• Autorzy: Bianchi M.P. , Mereghetti C. , Palano B. , Pighizzini G.
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

probabilistic automata; nondeterministic automata; descriptional complexity; unary languages

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2011
• Tom: Vol. 112, nr 2/3
• Strony: 119--135
• Opis fizyczny: Bibliogr. 12 poz.

Twórcy

autor

Bianchi M.P.

autor

Mereghetti C.

autor

Palano B.

autor

Pighizzini G.

• Dipartimento di Scienze dell’Informazione, Universita degli Studi di Milano, via Comelico 39, 20135 Milano, Italy,

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