Name
Abstract | ||
|---|---|---|
It is shown that if two PD0L forms F 1 and F 2 are form equivalent, i.e., generate the same family of languages, then the PD0L sequences E ( F 1 ) and E ( F 2 ) are isomorphic, provided one of the sequences contains a word of length greater than one. This result leads to a simple algorithm of deciding the form equivalence of two PD0L forms F 1 and F 2 . Moreover, we obtain the rather surprising result that F 1 and F 2 are form equivalent if and only if they are sequence equivalent, i.e., generate the same family of PD0L sequences (excluding again the trivial case that F 1 and F 2 generate only words of length one). |
Year | DOI | Venue |
|---|---|---|
1978 | 10.1016/0304-3975(78)90034-8 | Theor. Comput. Sci. |
DocType | Volume | Issue |
Journal | 6 | 2 |
ISSN | Citations | PageRank |
Theoretical Computer Science | 1 | 0.36 |
References | Authors | |
1 | 5 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| karel | 1 | 1129 | 251.15 |
| H.A. Maurer | 2 | 67 | 223.29 |
| Th. Ottmann | 3 | 468 | 124.40 |
| Keijo Ruohonen | 4 | 151 | 22.20 |
| Arto Salomaa | 5 | 2732 | 634.55 |