Fairness in context-free grammars under every choice-strategy (Q1122988): Difference between revisions
From MaRDI portal
Set profile property. |
ReferenceBot (talk | contribs) Changed an Item |
||
(One intermediate revision by one other user not shown) | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/0890-5401(89)90011-4 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2020188370 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3738540 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3862379 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3696524 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3783524 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Fair derivations in context-free grammars / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Fair derivations in E0L systems / rank | |||
Normal rank |
Latest revision as of 09:57, 20 June 2024
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