Fast nondeterministic recognition of context-free languages using two queues

DOI10.1016/S0020-0190(98)00091-XMaRDI QIDQ293326zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

formal languages

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

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

Cites work

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

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)