Name
Abstract | ||
|---|---|---|
This paper introduces Thue specifications, an approach for string-rewriting description of infinite graphs. It is shown that strongly reduction-bounded and unitary reduction-bounded rational Thue specifications have the same expressive power and both characterize the context-free graphs of Muller and Schupp. The problem of strong reduction-boundedness for rational Thue specifications is shown to be undecidable but the class of unitary reduction-bounded rational Thue specifications, that is a proper subclass of strongly reduction-bounded rational Thue specifications, is shown to be recursive. |
Year | DOI | Venue |
|---|---|---|
1998 | 10.1007/b71635 | FSTTCS |
Field | DocType | Volume |
Discrete mathematics,Combinatorics,Context-free grammar,Thue equation,Order theory,Turing machine,Unitary state,Rewriting,Mathematics,Recursion,Undecidable problem | Conference | 1530 |
ISSN | ISBN | Citations |
0302-9743 | 3-540-65384-8 | 9 |
PageRank | References | Authors |
0.81 | 8 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Hugues Calbrix | 1 | 34 | 2.63 |
| Teodor Knapik | 2 | 222 | 16.13 |