|
|||||
|
|
An infinite hierarchy induced by depth synchronization |
|
| Authors: | Franziska Biegler Ian McQuillan Kai Salomaa |
| Affiliation: | 1. Department of Computer Science, University of Western Ontario, London, ON, N6A 5B7, Canada;2. Department of Computer Science, University of Saskatchewan, Saskatoon, SK S7N 5A9, Canada;3. School of Computing, Queen’s University, Kingston, ON K7L 3N6, Canada |
| 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. |
| Keywords: | Synchronization ET0L languages Regulated rewriting Infinite hierarchy |
| 本文献已被 ScienceDirect 等数据库收录！ | |