The component hierarchy of chain-free cooperating distributed regular tree grammars
| Autor: | Zoltán Fülöp, G. Dányi |
|---|---|
| Rok vydání: | 2001 |
| Předmět: |
Discrete mathematics
K-ary tree General Computer Science Hierarchy (mathematics) Chomsky hierarchy Regular tree grammars Cooperating grammar systems Tree languages Tree (graph theory) Theoretical Computer Science Tree structure Regular language Regular tree grammar Formal language Algorithm Mathematics Computer Science(all) |
| Zdroj: | Theoretical Computer Science. 262(1-2):229-240 |
| ISSN: | 0304-3975 |
| DOI: | 10.1016/s0304-3975(00)00192-4 |
| Popis: | In this paper we show that the component hierarchy of chain-free distributed regular tree grammars cooperating with terminal strategy is infinite with respect to tree language generating capacity. More exactly, we prove that cf-CD-RTG⊣(n)⊂cf-CD-RTG⊣(2(n−1)2+3), where n⩾1 and cf-CD-RTG⊣(n) denotes the class of tree languages generated by chain-free distributed regular tree grammars of at most n components cooperating with terminal strategy. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect