Name
Abstract | ||
|---|---|---|
Depth-synchronization measures the number of parallel derivation steps in a synchronized context-free (SCF) grammar. When not bounded by a constant the depth-synchronization measure of an SCF grammar is at least logarithmic and at most linear with respect to the word length. Languages with linear depth-synchronization measure and languages with a depth-synchronization measure in between logarithmic and linear are proven to exist. This gives rise to a strict infinite hierarchy within the family of SCF (and ET0L) languages. |
Year | DOI | Venue |
|---|---|---|
2006 | 10.1016/j.tcs.2007.07.031 | Theor. Comput. Sci. |
Keywords | DocType | Volume |
word length,depth-synchronization measure,SCF grammar,linear depth-synchronization measure,depth synchronization,strict infinite hierarchy,parallel derivation step | Conference | 387 |
Issue | ISSN | Citations |
2 | 0304-3975 | 1 |
PageRank | References | Authors |
0.37 | 5 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Franziska Biegler | 1 | 44 | 5.06 |
| Ian McQuillan | 2 | 97 | 24.72 |
| Kai Salomaa | 3 | 1311 | 138.71 |