A probabilistic model of computing with words. (English) Zbl 1075.68047
Summary: Computing in the traditional sense involves inputs with strings of numbers and symbols rather than words, where words mean probability distributions over input alphabet, and are different from the words in classical formal languages and automata theory. In this paper our goal is to deal with Probabilistic Finite Automata (PFAs), Probabilistic Turing Machines (PTMs), and Probabilistic Context-Free Grammars (PCFGs) by inputting strings of words (probability distributions). Specifically, (i) we verify that PFAs computing strings of words can be implemented by means of calculating strings of symbols (Theorem 1); (ii) we elaborate on PTMs with input strings of words, and particularly demonstrate by describing Example 2 that PTMs computing strings of words may not be directly performed through only computing strings of symbols, i.e., Theorem 1 may not hold for PTMs; (iii) we study PCFGs and thus PRGs with input strings of words, and prove that Theorem 1 does hold for PCFRs and PRGs (Theorem 2); a characterization of PRGs in terms of PFAs, and the equivalence between PCFGs and their Chomsky and Greibach normal forms, in the sense that the inputs are strings of words, are also presented. Finally, the main results obtained are summarized, and a number of related issues for further study are raised.
MSC:
| 68Q45 | Formal languages and automata |
| 68Q05 | Models of computation (Turing machines, etc.) (MSC2010) |
| 81P68 | Quantum computation |
Keywords:
Probabilistic finite automata; Probabilistic Turing machines; Probabilistic context-free grammars; Strings of words; Computing with words; Quantum automata; Quantum models of computationReferences:
| [1] | Adleman, L. M., Molecular computation of solutions to combinatorial problems, Science, 266, 1021-1023 (1994) |
| [2] | Ambainis, A.; Freivalds, R., One-way quantum finite automatastrengths, weaknesses and generalizations, (Proceedings of the 39th Annual Symposium on Foundations of Computer Science. Proceedings of the 39th Annual Symposium on Foundations of Computer Science, Palo Alfo, CA (1998)), 332-341 |
| [3] | Ambainis, A.; Nayak, A.; Ta-Shma, A.; Vazirani, U., Dense quantum coding and quantum finite automata, J. ACM, 49, 4, 496-511 (2002) · Zbl 1326.68133 |
| [4] | Aho, A. V.; Ullman, J. D., The Theory of Parsing, Translation, and Compiling (1973), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ · Zbl 0309.68068 |
| [5] | Broadsky, A.; Pippenger, N., Characterizations of 1-way quantum finite automata, SIAM J. Comput., 31, 1456-1478 (2002) · Zbl 1051.68062 |
| [6] | Booth, T. L.; Thompson, R. A., Applying probability measures to abstract languages, IEEE Trans. Comput., C-22, 5, 442-450 (1973) · Zbl 0252.68033 |
| [7] | Bernstein, E.; Vazirani, U., Quantum complexity theory, SIAM J. Comput., 26, 5, 1411-1473 (1997) · Zbl 0895.68042 |
| [8] | Deutsch, D., Quantum theory, the Church-Turing principle and the universal quantum computer, Proc. R. Soc. London Ser. A, 400, 97-117 (1985) · Zbl 0900.81019 |
| [9] | K. De Leeuw, E.F. Moore, C.E. Shannon, N. Shapiro, Computability by probabilistic machines, in: C.E. Shannon, J. McCarthy (Eds.), Automata Studies, Annals of Mathematics Studies, vol. 34, Princeton University Press, Princeton, NJ, 1956, pp. 183-212.; K. De Leeuw, E.F. Moore, C.E. Shannon, N. Shapiro, Computability by probabilistic machines, in: C.E. Shannon, J. McCarthy (Eds.), Automata Studies, Annals of Mathematics Studies, vol. 34, Princeton University Press, Princeton, NJ, 1956, pp. 183-212. · Zbl 0074.11204 |
| [10] | C.A. Ellis, Probabilistic Languages and Automata, Ph.D. Dissertation, University of IL, Urbana, IL, 1969.; C.A. Ellis, Probabilistic Languages and Automata, Ph.D. Dissertation, University of IL, Urbana, IL, 1969. |
| [11] | R. Freivalds, Probabilistic two-way machines, in: Proceedings of the International Symposium on Mathematical Foundations of Computer Science. Lecture Notes in Computer Science, vol. 118, Springer-Verlag, New York, 1981, pp. 33-45.; R. Freivalds, Probabilistic two-way machines, in: Proceedings of the International Symposium on Mathematical Foundations of Computer Science. Lecture Notes in Computer Science, vol. 118, Springer-Verlag, New York, 1981, pp. 33-45. · Zbl 0486.68045 |
| [12] | Fu, K. S., Syntactic Pattern Recognition and Applications (1982), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ · Zbl 0521.68091 |
| [13] | Gill, J., Computational complexity of probabilistic turing machines, SIAM J. Comput., 6, 4, 675-695 (1977) · Zbl 0366.02024 |
| [14] | Gruska, J., Quantum Computing (1999), McGraw-Hill: McGraw-Hill London |
| [15] | Gudder, S., Quantum computers, Int. J. Theoret. Phys., 39, 2151-2177 (2000) · Zbl 1049.81013 |
| [16] | Gupta, S.; Zia, R. K.P., Quantum neural networks, J. Comput. System Sci., 63, 355-383 (2001) · Zbl 1006.68049 |
| [17] | Hopcroft, J. E.; Ullman, J. D., Introduction to Automata Theory, Languages, and Computation (1979), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0196.01701 |
| [18] | I. Macarie, Closure properties of stochastic languages, Technical Report TR441, Department of Computer Science, University of Rochester, Rochester, NY, 1993.; I. Macarie, Closure properties of stochastic languages, Technical Report TR441, Department of Computer Science, University of Rochester, Rochester, NY, 1993. |
| [19] | Moore, C.; Crutchfield, J. P., Quantum automata and quantum grammars, Theoret. Comput. Sci., 237, 275-306 (2000) · Zbl 0939.68037 |
| [20] | Motwani, R.; Raghavan, P., Randomized Algorithms (1995), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0849.68039 |
| [21] | Ney, H., Stochastic Grammars and pattern recognition, (Laface, P.; De Mori, R., Speech Recognition and UnderstandingRecent Advances (1992), Springer: Springer New York), 319-344 |
| [22] | Papadimitriou, C. M., Computational Complexity (1994), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0833.68049 |
| [23] | Paz, A., Introduction to Probabilistic Automata (1971), Academic Press: Academic Press New York · Zbl 0234.94055 |
| [24] | Qiu, D. W., Characterization of sequential quantum machines, Internat. J. Theoret. Phys., 41, 5, 811-822 (2002) · Zbl 1019.81009 |
| [25] | Qiu, D. W., Quantum pushdown automata, Int. J. Theoret. Phys., 41, 9, 1627-1639 (2002) · Zbl 1013.81006 |
| [26] | Qiu, D. W., Automata theory based on complete residuated lattice-valued logic(I), Sci. China (F), 44, 6, 419-429 (2001) · Zbl 1125.68383 |
| [27] | Qiu, D. W., Automata theory based on complete residuated lattice-valued logic(II), Sci. China (F), 45, 6, 442-452 (2002) · Zbl 1161.68549 |
| [28] | Rabin, M. O., Probabilistic automata, Inform. Control, 6, 230-245 (1963) · Zbl 0182.33602 |
| [29] | Salomaa, A., Probabilistic and weighted grammars, Inform. Control, 15, 529-544 (1969) · Zbl 0188.03201 |
| [30] | Santos, E. S., Probabilistic Turing machines and computability, Proc. Amer. Math. Soc., 22, 704-710 (1969) · Zbl 0186.01202 |
| [31] | Siegelmann, H. T., Neural Networks and Analog ComputationBeyond the Turing Limit (1999), Birkhauser: Birkhauser Boston · Zbl 0912.68161 |
| [32] | Thompson, R. A., Determination of probabilistic grammars for functionally specified probability-measure languages, IEEE Trans. Comput., C-23, 6, 603-614 (1974) · Zbl 0287.68050 |
| [33] | Wetherell, C. S., Probabilistic languagesa review and some open questions, Comput. Surveys, 12, 4, 361-379 (1980) · Zbl 0466.68073 |
| [34] | Wang, H.; Qiu, D. W., Computing with words via Turing machinesa formal approach, IEEE Trans. Fuzzy Systems, 11, 6, 707-718 (2003) |
| [35] | Yao, A. C., Quantum circuit complexity, (Proceedings of the 34th IEEE Symposium on Foundations of Computer Science (1993)), 352-361 |
| [36] | Ying, M. S., A formal model of computing with words, IEEE Trans. Fuzzy Systems, 10, 5, 640-652 (2002) |
| [37] | Zadeh, L. A., Fuzzy logic, neural networks and soft computing, Commun. ACM, 37, 3, 77-84 (1994) · Zbl 0831.68080 |
| [38] | Zadeh, L. A., Fuzzy Logic Computing with Words, IEEE Trans. Fuzzy Systems, 4, 2, 103-111 (1996) |
| [39] | Zadeh, L. A., From computing with numbers to computing with words-From manipulation of measurements to manipulation of perceptions, Ann. NY Acad. Sci., 929, 221-252 (2001) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
