Syntactic complexities of six classes of star-free languages

DOI10.25596/JALC-2012-083MaRDI QIDQ5178449zbMATH OpenFDO

Authors Baiyu Li, David Liu, Janusz Brzozowski

Publication date 16 March 2015

Full work available at URL https://doi.org/10.25596/JALC-2012-083

zbMATH Keywords

cofinite languagedefinite languagefinite automatonfinite languagemonotonic automatonpartially monotonic automatonreverse definite languagestar-free languagesyntactic complexitysyntactic semigroup

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• Syntactic complexities of some classes of star-free languages
• Syntactic complexity of prefix-, suffix-, bifix-, and factor-free regular languages
• Syntactic complexity of prefix-, suffix-, and bifix-free regular languages
• Syntactic complexity of \({\mathcal R}\)- and \({\mathcal J}\)-trivial regular languages
• Syntactic complexity of \(\mathcal{R}\)- and \(\mathcal{J}\)-trivial regular languages

Cited in

(15)

• On syntactic complexity of circular semi-flower automata
• Syntactic complexity of suffix-free languages
• Descriptional complexity of regular languages
• The syntactic complexity of semi-flower languages
• Syntactic complexity of bifix-free regular languages
• Syntactic complexity of bifix-free languages
• Checking whether an automaton is monotonic is NP-complete
• Syntactic complexities of some classes of star-free languages
• On the Complexity of the Syntax of Tree Languages
• scientific article; zbMATH DE number 1254105 (Why is no real title available?)
• Nondeterministic state complexity of star-free languages
• Forbidden patterns for ordered automata
• Syntactic complexity of prefix-, suffix-, and bifix-free regular languages
• Completing Wheeler automata
• Syntactic complexity of regular ideals

This page was built for publication: Syntactic complexities of six classes of star-free languages

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