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

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

zbMATH Keywords

look-ahead on pushdowns

0 references

iterated pushdown languages

0 references

LL(k) iterated indexed grammars

0 references

iterated pushdown automata

0 references

MaRDI profile type

MaRDI publication profile

0 references

full work available at URL

https://doi.org/10.1016/0890-5401(87)90014-9

0 references

cites work

Indexed Grammars—An Extension of Context-Free Grammars

0 references

Nested Stack Automata

0 references

LR-regular grammars - an extension of LR(k) grammars

0 references

The IO- and OI-hierarchies

0 references

An automata-theoretical characterization of the OI-hierarchy

0 references

Top-down tree transducers with regular look-ahead

0 references

On tree transducers for partial functions

0 references

Fixed Point Languages, Equality Languages, and Representation of Recursively Enumerable Languages

0 references

IO and OI. II

0 references

Pushdown machines for the macro tree transducer

0 references

Macro tree transducers

0 references

Q3738591

0 references

Q4089754

0 references

A Note on Pushdown Store Automata and Regular Systems

0 references

Full AFLs and nested iterated substitution

0 references

Q4198075

0 references

Q5592246

0 references

LL-regular grammars

0 references

A generalized approach to formal languages

0 references

Q4077463

0 references

Parsing macro grammars top down

0 references

Ll-regular grammars

0 references

The equivalence problem for LL- and LR-regular grammars

0 references

Q3964031

0 references

Q3667962

0 references

On deterministic indexed languages

0 references

Closure properties of deterministic indexed languages

0 references

Q3698329

0 references

On LL-regular grammars

0 references

Some definitional suggestions for automata theory

0 references

Parsers for indexed grammars

0 references

Q4061986

0 references

Identifiers

zbMATH Open document ID

0625.68063

0 references

DOI

10.1016/0890-5401(87)90014-9

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:579952

@@ 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.
+Normal rank
@@ Property / Mathematics Subject Classification ID @@
+Q45
@@ Property / Mathematics Subject Classification ID: 68Q45 / rank @@
+Normal rank
@@ Property / Mathematics Subject Classification ID @@
+N20
@@ Property / Mathematics Subject Classification ID: 68N20 / rank @@
+Normal rank
@@ Property / zbMATH DE Number @@
+4016221
@@ 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
@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / full work available at URL @@
+https://doi.org/10.1016/0890-5401(87)90014-9
+Normal rank
@@ Property / OpenAlex ID @@
+W1995721258
@@ Property / OpenAlex ID: W1995721258 / rank @@
+Normal rank
@@ Property / cites work @@
+Indexed Grammars—An Extension of Context-Free Grammars
+Normal rank
@@ Property / cites work @@
+Nested Stack Automata
@@ Property / cites work: Nested Stack Automata / rank @@
+Normal rank
@@ Property / cites work @@
+LR-regular grammars - an extension of LR(k) grammars
+Normal rank
@@ Property / cites work @@
+The IO- and OI-hierarchies
@@ Property / cites work: The IO- and OI-hierarchies / rank @@
+Normal rank
@@ Property / cites work @@
+An automata-theoretical characterization of the OI-hierarchy
+Normal rank
@@ Property / cites work @@
+Top-down tree transducers with regular look-ahead
@@ Property / cites work: Top-down tree transducers with regular look-ahead / rank @@
+Normal rank
@@ Property / cites work @@
+On tree transducers for partial functions
@@ Property / cites work: On tree transducers for partial functions / rank @@
+Normal rank
@@ Property / cites work @@
+Fixed Point Languages, Equality Languages, and Representation of Recursively Enumerable Languages
+Normal rank
@@ Property / cites work @@
+IO and OI. II
@@ Property / cites work: IO and OI. II / rank @@
+Normal rank
@@ Property / cites work @@
+Pushdown machines for the macro tree transducer
@@ Property / cites work: Pushdown machines for the macro tree transducer / rank @@
+Normal rank
@@ Property / cites work @@
+Macro tree transducers
@@ Property / cites work: Macro tree transducers / rank @@
+Normal rank
@@ Property / cites work @@
+Q3738591
@@ Property / cites work: Q3738591 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4089754
@@ Property / cites work: Q4089754 / rank @@
+Normal rank
@@ Property / cites work @@
+A Note on Pushdown Store Automata and Regular Systems
+Normal rank
@@ Property / cites work @@
+Full AFLs and nested iterated substitution
@@ Property / cites work: Full AFLs and nested iterated substitution / rank @@
+Normal rank
@@ Property / cites work @@
+Q4198075
@@ Property / cites work: Q4198075 / rank @@
+Normal rank
@@ Property / cites work @@
+Q5592246
@@ Property / cites work: Q5592246 / rank @@
+Normal rank
@@ Property / cites work @@
+LL-regular grammars
@@ Property / cites work: LL-regular grammars / rank @@
+Normal rank
@@ Property / cites work @@
+A generalized approach to formal languages
@@ Property / cites work: A generalized approach to formal languages / rank @@
+Normal rank
@@ Property / cites work @@
+Q4077463
@@ Property / cites work: Q4077463 / rank @@
+Normal rank
@@ Property / cites work @@
+Parsing macro grammars top down
@@ Property / cites work: Parsing macro grammars top down / rank @@
+Normal rank
@@ Property / cites work @@
+Ll-regular grammars
@@ Property / cites work: Ll-regular grammars / rank @@
+Normal rank
@@ Property / cites work @@
+The equivalence problem for LL- and LR-regular grammars
+Normal rank
@@ Property / cites work @@
+Q3964031
@@ Property / cites work: Q3964031 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3667962
@@ Property / cites work: Q3667962 / rank @@
+Normal rank
@@ Property / cites work @@
+On deterministic indexed languages
@@ Property / cites work: On deterministic indexed languages / rank @@
+Normal rank
@@ Property / cites work @@
+Closure properties of deterministic indexed languages
+Normal rank
@@ Property / cites work @@
+Q3698329
@@ Property / cites work: Q3698329 / rank @@
+Normal rank
@@ Property / cites work @@
+On LL-regular grammars
@@ Property / cites work: On LL-regular grammars / rank @@
+Normal rank
@@ Property / cites work @@
+Some definitional suggestions for automata theory
@@ Property / cites work: Some definitional suggestions for automata theory / rank @@
+Normal rank
@@ Property / cites work @@
+Parsers for indexed grammars
@@ Property / cites work: Parsers for indexed grammars / rank @@
+Normal rank
@@ Property / cites work @@
+Q4061986
@@ Property / cites work: Q4061986 / rank @@
+Normal rank
@@ links / mardi / name / links / mardi / name @@
+Publication:579952