Fast nondeterministic recognition of context-free languages using two queues

DOI10.1016/S0020-0190(98)00091-XzbMATH Open1338.68159OpenAlexW2073171949MaRDI QIDQ293326FDOQ293326

Authors: Burton Rosenberg 

Publication date: 9 June 2016

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: http://www.sciencedirect.com/science/article/pii/S002001909800091X?np=y

Recommendations

• scientific article; zbMATH DE number 3958761
• Fast recognition of pushdown automaton and context-free languages
• scientific article; zbMATH DE number 3978426
• Parallel recognition and ranking of context-free languages
• Parallel time O(log n) recognition of unambiguous context-free languages
• On the parallel recognition of unambiguous context-free languages
• Almost optimal sublinear time parallel recognition algorithms for three subclasses of context free languages
• Upper bounds on recognition of a hierarchy of non-context-free languages
• An efficient recognizer for the Boolean closure of context-free languages

zbMATH Keywords

formal languages

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cites Work

• Tape versus queue and stacks: The lower bounds
• On the intersection of stacks and queues
• Reset machines
• Automates a file
• Multiple equality sets and Post machines
• QRT FIFO automata, breadth-first grammars and their relations
• Über einen Automaten mit Pufferspeicherung
• The Power of the Queue
• On the power of several queues

Cited In (1)

• A lower bound for the nondeterministic space complexity of context-free recognition

This page was built for publication: Fast nondeterministic recognition of context-free languages using two queues

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q293326)