Widths of regular and context-free languages

DOI10.4230/LIPICS.FSTTCS.2019.49MaRDI QIDQ5875688zbMATH OpenFDO

Authors David Mestel

Publication date 3 February 2023

Full work available at URL https://arxiv.org/abs/1709.08696

zbMATH Keywords

combinatorics on wordsformal languagesinformation flow

Mathematics Subject Classification ID

Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.) (68N30) Theory of computing (68Qxx)

Recommendations

• Nondeterministic tree width of regular languages
• On the density of regular and context-free languages
• On the Density of Regular and Context-Free Languages
• Partial orders on words, minimal elements of regular languages, and state complexity
• Finding the growth rate of a regular or context-free language in polynomial time

Cited in

(5)

• Estimating the Size of Context-Free Tiling Languages
• scientific article; zbMATH DE number 176932 (Why is no real title available?)
• The big-O problem for labelled Markov chains and weighted automata
• The big-O problem
• On deterministic finite automata equipped with partial orders

This page was built for publication: Widths of regular and context-free languages

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