Space- and Time-Bounded Nondeterminism for Cellular Automata

• Autorzy: Kutrib M. , Löwe J-T.
• Języki publikacji: EN

Abstrakty

EN

Nondeterministic cellular language acceptors are investigated. The nondeterminism is regarded as limited resource. For parallel devices it is natural to bound the nondeterminism in time and/or space. Depending on the length of the input, the number of allowed nondeterministic state transitions as well as the number of nondeterministic cells at all, is limited. For space-bounded nondeterminism it is shown that k+1 cells are not better than k, in case of one-way information flow. In the two-way case, one cell gains the power of unlimited nondeterminism. For the important real-time one-way arrays the range between deterministic and one guess per cell computations is studied. It is proved that there exists an infinite hierarchy of properly included families. By considering the relations with context-free languages, several relations between the devices in question are implied. Finally, a diagram is presented that summarizes relations between many cellular classes.

Słowa kluczowe

EN

cellular automata; formal languages; limited nondeterminism; parallel computing

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2003
• Tom: Vol. 58, nr 3,4
• Strony: 273--293
• Opis fizyczny: Bibliogr. 27 poz., wykr.

Twórcy

autor

Kutrib M.

• Institute of Informatics, University of Giessen, Arndstr. 2, D-35392 Giessen, Germany

autor

Löwe J-T.

• Institute of Informatics, University of Giessen, Arndstr. 2, D-35392 Giessen, Germany

Bibliografia

• [1] Buchholz, Th., Klein. A., Kutrib, М.: On interacting automata with limited nondeterminism. Fundamenta Informaticae, 52, 2002, 15-38.
• [2] Buchholz, Th., Kutrib, М.: On the power of one-way bounded cellular time computers. Developments in Language Theory (S. Bozapalidis, Ed.), Aristotle University of Thessaloniki, Thessaloniki, Greece, 1997.
• [3] Buchholz, Th., Kutrib, М.: Some relations between massively parallel arrays, Parallel Computing, 23, 1997, 1643-1662.
• [4] Buchholz, Th., Kutrib, М.: On time computability of functions in one-way cellular automata, Acta Informática. 35, 1998, 329-352.
• [5] Chang, J. H., Ibarra, О. H., Vergis, A.: On the power of one-way communication. Journal of the ACM, 35, 1988,697-726.
• [6] Ćulik II, K., Yu, S.: Iterative tree automata. Theoretical Computer Science, 32, 1984, 227-247.
• [7] Dyer. C. R.: One-way bounded cellular automata. Information and Control. 44, 1980, 261-281.
• [8] Fischer, P. C., Kintala, C. M. R.: Real-time computations with restricted nondeterminism. Mathematical Systems Theory, 12, 1979, 219-231.
• [9] Goldsmith. J., Levy, M. A., Mundhenk. M.: Limited nondeterminism, SIGACT News, 27, 1996. 20-29.
• [10] Goldstine, J., Kintala, C., Wotschke. D.: On measuring nondeterminism in regular languages, Information and Computation. 86, 1990, 179-194.
• [11] Goldstine, J., Leung, H„ Wotschke, D.: On the relation between ambiguity and nondeterminism in finite automata. Information and Computation. 100, 1992, 261-270.
• [12] Herzog, C.: Pushdown automata with bounded nondeterminism and bounded ambiguity, Theoretical Computer Science, 181, 1997. 141-157.
• [13] Hromkovic, J., Karhumäki, J., Klauck, H., Schnitger, G., Seibert, S.: Measures of nondeterminism in finite automata. International Colloquium on Automata. Languages and Programming, LNCS 1853, Springer-Verlag, Berlin, 2000.
• [14] Ibarra, О. H., Jiang, Т.: On one-way cellular arrays, SIAM Journal on Computing, 16, 1987. I 135-1154.
• [15] Ibarra, O. H., Kim, S. М.: Characterizations and computational complexity of systolic trellis automata. Theoretical Computer Science, 29, 1984, 123-153.
• [16] Kintala. C. М.: Computations with a restricted number of nondeterministic steps, Ph.D. Thesis, Pennsylvania State University, 1977.
• [17] Kintala, C. М., Fischer, P. C.: Refining nondeterminism in relativized complexity classes, SIAM Journal on Computing, 13. 1984. 329-337.
• [18] Kintala, C. M., Wotschke, D.: Amounts of nondeterminism in finite automata, Acta Informática, 13. 1980. 199-204.
• [19] Matamala, M.: Alternation on cellular automata, Theoretical Computer Science, 180, 1997, 229-241.
• [20] Mazoyer, J., Terrier, V.: Signals in one-dimensional cellular automata. Theoretical Computer Science, 217, 1999,53-80.
• [21] Salomaa, K., Yu. S.: Limited nondeterminism for pushdown automata, Bulletin of the European Association for Theoretical Computer Science, 50, 1993, 186-193.
• [22] Salomaa, K., Yu, S.: Measures of nondeterminism for pushdown automata, Journal of Computer and System Sciences. 49. 1994, 362-374.
• [23] Seidel, S. R.: Language Recognition and the Synchronization of Cellular Automata, Technical Report 79-02, Department of Computer Science, University of Iowa, Iowa City, 1979.
• [24] Smith III, A. R.: Cellular automata and formal languages, IEEE Symposium on Switching and Automata Theory IEEE. 1970.
• [25] Smith П1, A. R.: Real-time language recognition by one-dimensional cellular automata, Journal of Computer and System Sciences, 6, 1972, 233-253.
• [26] Terrier, V.: On real time one-way cellular array, Theoretical Computer Science, 141, 1995, 331-335.
• [27] Vermeir, D., Savitch. W.: On the amount of nondeterminism in pushdown automata, Fundamenta Informaticae, 4, 1981,401-418.