Recent trends in descriptional complexity of formal languages

MaRDI QIDQ4967154zbMATH OpenFDO

Authors Martin Kutrib, Giovanni Pighizzini

Publication date 3 July 2019

Full work available at URL http://bulletin.eatcs.org/index.php/beatcs/article/view/208/202

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• Descriptional complexity -- an introductory survey
• Descriptional complexity of regular languages
• scientific article; zbMATH DE number 7699973
• State complexity of regular languages
• Descriptional complexity of machines with limited resources

Cited in

(13)

• Structural properties of NFAs and growth rates of nondeterminism measures
• Modern aspects of complexity within formal languages
• State complexity of prefix distance
• State complexity of permutation on finite languages over a binary alphabet
• State complexity of prefix distance
• Descriptional complexity -- an introductory survey
• scientific article; zbMATH DE number 2068876 (Why is no real title available?)
• Branching measures and nearly acyclic NFAs
• State complexity of suffix distance
• Descriptional complexity of machines with limited resources
• State complexity of deletion and bipolar deletion
• State complexity of inversion operations
• Operational state complexity of unary NFAs with finite nondeterminism

This page was built for publication: Recent trends in descriptional complexity of formal languages

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