Look-ahead on pushdowns (Q579952): Difference between revisions

From MaRDI portal
Importer (talk | contribs)
Created a new Item
 
Importer (talk | contribs)
Changed an Item
Property / review text
 
The general notion of look-ahead on pushdowns is used to prove that (1) the deterministic iterated pushdown languages are closed under complementation, (2) the deterministic iterated pushdown languages are properly included in the nondeterministic iterated pushdown languages; the counter example is a very simple linear context-free language, independent of the amount of iteration, (3) LL(k) iterated indexed grammars can be parsed by deterministic iterated pushdown automata, and (4) it is decidable whether an iterated indexed grammar is LL(k). Analogous results hold for iterated pushdown automata with regular look- ahead on the input, and LL-regular iterated indexed grammars.
Property / review text: The general notion of look-ahead on pushdowns is used to prove that (1) the deterministic iterated pushdown languages are closed under complementation, (2) the deterministic iterated pushdown languages are properly included in the nondeterministic iterated pushdown languages; the counter example is a very simple linear context-free language, independent of the amount of iteration, (3) LL(k) iterated indexed grammars can be parsed by deterministic iterated pushdown automata, and (4) it is decidable whether an iterated indexed grammar is LL(k). Analogous results hold for iterated pushdown automata with regular look- ahead on the input, and LL-regular iterated indexed grammars. / rank
 
Normal rank
Property / Mathematics Subject Classification ID
 
Property / Mathematics Subject Classification ID: 68Q45 / rank
 
Normal rank
Property / Mathematics Subject Classification ID
 
Property / Mathematics Subject Classification ID: 68N20 / rank
 
Normal rank
Property / zbMATH DE Number
 
Property / zbMATH DE Number: 4016221 / rank
 
Normal rank
Property / zbMATH Keywords
 
look-ahead on pushdowns
Property / zbMATH Keywords: look-ahead on pushdowns / rank
 
Normal rank
Property / zbMATH Keywords
 
iterated pushdown languages
Property / zbMATH Keywords: iterated pushdown languages / rank
 
Normal rank
Property / zbMATH Keywords
 
LL(k) iterated indexed grammars
Property / zbMATH Keywords: LL(k) iterated indexed grammars / rank
 
Normal rank
Property / zbMATH Keywords
 
iterated pushdown automata
Property / zbMATH Keywords: iterated pushdown automata / rank
 
Normal rank

Revision as of 17:33, 1 July 2023

scientific article
Language Label Description Also known as
English
Look-ahead on pushdowns
scientific article

    Statements

    Look-ahead on pushdowns (English)
    0 references
    0 references
    0 references
    1987
    0 references
    The general notion of look-ahead on pushdowns is used to prove that (1) the deterministic iterated pushdown languages are closed under complementation, (2) the deterministic iterated pushdown languages are properly included in the nondeterministic iterated pushdown languages; the counter example is a very simple linear context-free language, independent of the amount of iteration, (3) LL(k) iterated indexed grammars can be parsed by deterministic iterated pushdown automata, and (4) it is decidable whether an iterated indexed grammar is LL(k). Analogous results hold for iterated pushdown automata with regular look- ahead on the input, and LL-regular iterated indexed grammars.
    0 references
    look-ahead on pushdowns
    0 references
    iterated pushdown languages
    0 references
    LL(k) iterated indexed grammars
    0 references
    iterated pushdown automata
    0 references

    Identifiers