On minimal grammar problems for finite languages

DOI10.1007/978-3-319-98654-8_28MaRDI QIDQ1622981zbMATH OpenOpenAlexFDO

Authors Hermann Gruber, Markus Holzer, Simon Wolfsteiner

Publication date 22 November 2018

Full work available at URL https://doi.org/10.1007/978-3-319-98654-8_28

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• On the context-free production complexity of finite languages
• On the grammatical complexity of finite languages
• On the complexity of the smallest grammar problem over fixed alphabets
• On the cover complexity of finite languages
• Cover complexity of finite languages

Cited in

(13)

• On the cover complexity of finite languages
• scientific article; zbMATH DE number 7559421 (Why is no real title available?)
• Finding the smallest binarization of a CFG is NP-hard
• scientific article; zbMATH DE number 1560210 (Why is no real title available?)
• On the number of rules needed for the automaton grammar to generate a finite language
• On minimizing regular expressions without Kleene star
• On the complexity of the smallest grammar problem over fixed alphabets
• Lower bounds for context-free grammars
• On the grammatical complexity of finite languages
• scientific article; zbMATH DE number 3924157 (Why is no real title available?)
• Minimalist Grammars and Minimalist Categorial Grammars: Toward Inclusion of Generated Languages
• On the compressibility of finite languages and formal proofs
• scientific article; zbMATH DE number 6819783 (Why is no real title available?)

This page was built for publication: On minimal grammar problems for finite languages

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