Normal form algorithms for extended context-free grammars

DOI10.1016/S0304-3975(00)00294-2MaRDI QIDQ5958723zbMATH OpenWikidataFDO

Authors J. Albert, Dora Giammarresi, D. Wood

Publication date 3 March 2002

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

Full work available at URL https://doi.org/10.1016/S0304-3975(00)00294-2

zbMATH Keywords

complexityefficient algorithmsextended context-free grammarsgrammatical representationsnormal formssymbolic manipulation

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42)

Recommendations

• scientific article; zbMATH DE number 1452979
• scientific article; zbMATH DE number 2201369
• Greibach normal form transformation revisited.
• Complexity of normal form grammars
• On normal form grammars and their size

Cites work

• \textit{Grail}: A C++ library for automata and expressions
• A New Normal-Form Theorem for Context-Free Phrase Structure Grammars
• An easy proof of Greibach normal form
• Dagwood
• Derivatives of Regular Expressions
• Eliminating null rules in linear time
• Greibach normal form transformation revisited.
• scientific article; zbMATH DE number 3609156 (Why is no real title available?)
• scientific article; zbMATH DE number 3639163 (Why is no real title available?)
• scientific article; zbMATH DE number 1117894 (Why is no real title available?)
• scientific article; zbMATH DE number 194974 (Why is no real title available?)
• scientific article; zbMATH DE number 3323547 (Why is no real title available?)
• scientific article; zbMATH DE number 3413820 (Why is no real title available?)
• On the equivalence, containment, and covering problems for the regular and context-free languages
• Optimization of LR(k) parsers

Cited in

(18)

• Estimating the execution complexity of logical specifications based on context-free grammars
• Attribute grammars for unranked trees as a query language for structured documents
• Generalized register context-free grammars
• Deciding twig-definability of node selecting tree automata
• A uniform framework for problems on context-free grammars
• COMAR: a Data Format for Integration of CFG Tools
• Normal forms for context-free node-rewriting hypergraph grammars
• A formalisation of the normal forms of context-free grammars in HOL4
• Generating, sampling and counting subclasses of regular tree languages
• Simplifying XML schema: single-type approximations of regular tree languages
• scientific article; zbMATH DE number 637403 (Why is no real title available?)
• scientific article; zbMATH DE number 1951550 (Why is no real title available?)
• scientific article; zbMATH DE number 1962786 (Why is no real title available?)
• On normal form grammars and their size
• scientific article; zbMATH DE number 1452979 (Why is no real title available?)
• scientific article; zbMATH DE number 2201369 (Why is no real title available?)
• scientific article; zbMATH DE number 4189198 (Why is no real title available?)
• Schemas for unordered XML on a DIME

Describes a project that uses

Uses Software

• Grail

This page was built for publication: Normal form algorithms for extended context-free grammars

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