## Abstract

In an earlier paper, results of a research project to define grammars and automata of two and three dimensions were reported. In that paper, many of the relevant theorems were only discussed in a cursory way, and were not formally proved. In this paper we formalize the major concepts introduced. Because of current interest and the fact that the two-dimensional grammars and automata defined are but a special case of the three-dimensional grammars and automata, we concentrate on three-dimensional concepts. A brief overview of current three-dimensional grammars and automata is given. Formal definitions for random context structure grammars and random context structure automata are given. A formal proof is given for the equivalence of the class of languages generated by random context structure grammars and the class of languages accepted by random context structure grammars.

Original language | English |
---|---|

Pages (from-to) | 159-183 |

Number of pages | 25 |

Journal | Information Sciences |

Volume | 53 |

Issue number | 1-2 |

DOIs | |

Publication status | Published - Jan 1991 |

## ASJC Scopus subject areas

- Software
- Control and Systems Engineering
- Theoretical Computer Science
- Computer Science Applications
- Information Systems and Management
- Artificial Intelligence