Normal form algorithms for extended context-free grammars

DOI10.1016/S0304-3975(00)00294-2zbMath0984.68092MaRDI QIDQ5958723

Dora Giammarresi, Derick Wood, Juergen Albert

Publication date: 3 March 2002

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

complexity; normal forms; symbolic manipulation; efficient algorithms; extended context-free grammars; grammatical representations

Mathematics Subject Classification ID

68Q42: Grammars and rewriting systems

Related Items

Deciding twig-definability of node selecting tree automata, Generating, sampling and counting subclasses of regular tree languages, Simplifying XML schema: single-type approximations of regular tree languages, Schemas for unordered XML on a DIME, Attribute grammars for unranked trees as a query language for structured documents

Uses Software

• Grail

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the equivalence, containment, and covering problems for the regular and context-free languages
• \textit{Grail}: A C++ library for automata and expressions
• Greibach normal form transformation revisited.
• Optimization of LR(k) parsers
• An easy proof of Greibach normal form
• Eliminating null rules in linear time
• Dagwood
• A New Normal-Form Theorem for Context-Free Phrase Structure Grammars
• Derivatives of Regular Expressions