On minimal grammar problems for finite languages

DOI10.1007/978-3-319-98654-8_28OpenAlexW2885627683MaRDI QIDQ1622981FDOQ1622981

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

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

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cited In (13)

• Title not available (Why is that?)
• On the cover complexity of finite languages
• Title not available (Why is that?)
• Finding the smallest binarization of a CFG is NP-hard
• 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
• Title not available (Why is that?)
• On the grammatical complexity of finite languages
• Minimalist Grammars and Minimalist Categorial Grammars: Toward Inclusion of Generated Languages
• On the compressibility of finite languages and formal proofs
• Title not available (Why is that?)

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)