Fairness in context-free grammars under every choice-strategy (Q1122988)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Fairness in context-free grammars under every choice-strategy |
scientific article |
Statements
Fairness in context-free grammars under every choice-strategy (English)
0 references
1989
0 references
Given a context-free grammar \(G=(N\), T, S, P), a production \(A\to x\) in P is said to be enabled in a sentential form z (along a derivation) iff z contains occurrences of A. A derivation d is called fair iff either it is finite or it is infinite and every rule that is infinitely many times enabled along d is infinitely many times applied along d. In a paper by \textit{S. Porat}, \textit{N. Francez}, \textit{S. Moran}, \textit{S. Zaks} [Inf. Control 55, 108-116 (1982; Zbl 0535.68038)], where this notion has been introduced, the fairly terminating grammars are characterized as non- variable-doubling. In the present paper, it is proved that the same characterization is valid under canonical derivations, that is with the next variable to be rewritten deterministically chosen. Two families of canonical derivations are introduced and studied as special cases, the so-called spinal derivations and the layered derivations.
0 references
fairness
0 references
context-free grammars
0 references
fairly terminating grammars
0 references