The bounded degree problem for NLC grammars is decidable (Q579950)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Publication:579950 |
scientific article; zbMATH DE number 4016215
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | The bounded degree problem for NLC grammars is decidable |
scientific article; zbMATH DE number 4016215 |
Statements
The bounded degree problem for NLC grammars is decidable (English)
0 references
1986
0 references
The degree of a graph H is the maximum among the degrees of its nodes. A set of graphs L is of bounded degree if there exists a positive integer n such that the degree of each graph in L does not exceed n. We demonstrate that it is decidable whether or not the (graph) language of an arbitrary node label controlled (NLC) grammar is of bounded degree. Moreover, it is shown that, given an arbitrary NLC grammar G generating the language L(G) of bounded degree, one can effectively compute the maximum integer which appears as the degree of a graph in L(G).
0 references
node label controlled graph grammar
0 references
decision problems
0 references
degree of a graph
0 references
bounded degree
0 references
0 references
0.8355938196182251
0 references
0.7875543832778931
0 references
0.7774637937545776
0 references
0.769287645816803
0 references
