Name
Abstract | ||
|---|---|---|
A derivation relation is a total regulator on Σ ∗ if, for every language L ⊆ Σ ∗ , the set of all words derivable from L is a regular language. We show that for a wide class of derivation relations ⇒ P ∗ , ⇒ P ∗ is a total regulator on Σ ∗ if,and only if it is a well-quasi-order (wqo) on Σ ∗ . Using wqo theory, we give a characterization of all non-erasing pure context-free (0S) derivation relations which are total regulators. |
Year | DOI | Venue |
|---|---|---|
1985 | 10.1016/0304-3975(85)90162-8 | Theor. Comput. Sci. |
Keywords | Field | DocType |
derivation,unavoidable sets,context-free languages,well-quasi-orders,Formal languages,regular languages | Discrete mathematics,Computer science,If and only if,Regular language,Finite group | Journal |
Volume | Issue | ISSN |
40 | 2-3 | Theoretical Computer Science |
ISBN | Citations | PageRank |
3-540-15650-X | 10 | 0.93 |
References | Authors | |
6 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| W. Bucher | 1 | 43 | 8.31 |
| A. Ehrenfeucht | 2 | 1823 | 497.83 |
| David Haussler | 3 | 8327 | 3068.93 |