A hierarchy of random-context grammars and automata. (English) Zbl 0622.68065
Random-context grammars are progressively extended to three dimensions. Random-context structure grammars that generate three-dimensional digital structures are introduced. The characterization of random-context array grammars and random-context structure grammars by two-dimensional random- context array automata and three-dimensional random-context structure automata respectively is investigated. A possible practical application of random-context structure grammars and automata in the modeling of chemical molecules is speculated on.
MSC:
| 68Q45 | Formal languages and automata |
Keywords:
three-dimensional digital structures; random-context array grammars; random-context structure grammars; random-context array automata; random- context structure automata; modeling of chemical moleculesReferences:
| [1] | Van der Walt, A. P.J., Random context languages, (Information Processing 71 (1971)) · Zbl 0221.68047 |
| [2] | Von Solms, S. H., Die Karakterisering deur Outomate van Sommige Klasse Tale in die Kontekssensitiewe Gebied, (Ph.D. Thesis (1972), RAU: RAU Johannesburg) |
| [3] | Von Solms, S. H., The Characterization by automata of certain classes of languages in the context sensitive area, Inform. and Control, 27, 3, 262-271 (Mar. 1975) · Zbl 0308.68063 |
| [4] | Von Solms, S. H., Random context array grammars, (presented at ACM Computer Science Conference (1979)) · Zbl 0443.68071 |
| [5] | Von Solms, S. H., Random context array grammars, (Information Processing 80, Proceedings of IFIP Congress 80, North-Holland (1980)) · Zbl 0443.68071 |
| [6] | Rosenfeld, A., Picture Languages (1979), Academic · Zbl 0471.68074 |
| [7] | Inoue; Takanami; Nakamura, A note on two-dimensional finite automata, Inform. Process. Lett., No. 1 (Jan. 1978) · Zbl 0374.94036 |
| [8] | Inoue; Nakamura, Some properties of two-dimensional on-line tessellation acceptors, Inform. Sci., 13, 95-121 (1977) · Zbl 0371.94067 |
| [9] | E. M. Ehlers, Random Context Structure Grammars and Automata, Ph.D. Thesis, in preparation.; E. M. Ehlers, Random Context Structure Grammars and Automata, Ph.D. Thesis, in preparation. · Zbl 0717.68060 |
| [10] | Lest; Teaneck, Detection of three-dimensional patterns of atoms in chemical structures, Comm. ACM, 22, No. 4 (Apr. 1979) |
| [11] | A. Rosenfeld, Three-dimensional digital topology, Inform. and Control; A. Rosenfeld, Three-dimensional digital topology, Inform. and Control · Zbl 0484.68054 |
| [12] | Requicha, Representations for rigid solids: Theory, methods and systems, Comput. Surveys, 12, No. 4 (Dec. 1980) |
| [13] | Taniguichi; Inoue; Takanami, A note on three-dimensional finite automata, Inform. Sci., 26, 65-85 (1982) · Zbl 0485.68050 |
| [14] | Sampson, J. R., Biological Information Processing, Current Theory and Computer Simulation (1984), Wiley |
| [15] | Akingbehin, Biochip technology, SIGBIO Newsletter, 6, No. 4 (Mar. 1984) |
| [16] | Hopcroft; Ullman, Formal Languages and Their Relation to Automata (1969), Addison-Wesley · Zbl 0196.01701 |
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.
