Testing for grammatical coverings

DOI10.1016/0304-3975(85)90226-9MaRDI QIDQ1080663zbMATH OpenOpenAlexFDO

Authors Daniel J. Rosenkrantz, H. B. III Hunt

Publication date 1985

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

Full work available at URL https://doi.org/10.1016/0304-3975(85)90226-9

zbMATH Keywords

context-free grammarsgraph isomorphismNP-completepolynomial time algorithmsunambiguous context-free grammarsgrammar isomorphismgrammatical similarity relationsinterpretation of grammar formsonto grammar homomorphismReynolds covering

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• scientific article; zbMATH DE number 176240
• On the complexity of LL(k) testing
• scientific article; zbMATH DE number 4060748
• On derivation preservation
• The complexity of equivalence problems for commutative grammars

Cites work

• scientific article; zbMATH DE number 3671712 (Why is no real title available?)
• scientific article; zbMATH DE number 3727586 (Why is no real title available?)
• scientific article; zbMATH DE number 3461845 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• An Observation on Relative Parsing Time
• Bracketed context-free languages
• Context-free grammar forms
• Context-free grammars: covers, normal forms, and parsing
• Grammar and L forms: an introduction
• Isomorphism Testing for Graphs, Semigroups, and Finite Automata are Polynomially Equivalent Problems
• On strict interpretations of grammar forms
• On the Covering and Reduction Problems for Context-Free Grammars
• On the equivalence, containment, and covering problems for the regular and context-free languages
• The structure of context-free grammatical families
• Transformational classes of grammars

Cited in

(4)

• SLR(k) covering for LR(k) grammars
• Finding the smallest binarization of a CFG is NP-hard
• Controllable Combinatorial Coverage in Grammar-Based Testing
• On derivation preservation

This page was built for publication: Testing for grammatical coverings

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