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

zbMATH Keywords

finite automatonsyntactic complexityfinite languagesyntactic semigroupstar-free languagemonotonic automatoncofinite languagedefinite languagepartially monotonic automatonreverse definite language

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

(13)

• On the Complexity of the Syntax of Tree Languages
• On syntactic complexity of circular semi-flower automata
• Syntactic complexity of regular ideals
• Forbidden patterns for ordered automata
• Nondeterministic state complexity of star-free languages
• Checking whether an automaton is monotonic is NP-complete
• Syntactic complexity of suffix-free languages
• Syntactic complexities of some classes of star-free languages
• Syntactic complexity of prefix-, suffix-, and bifix-free regular languages
• The syntactic complexity of semi-flower languages
• Descriptional complexity of regular languages
• Syntactic complexity of bifix-free regular languages
• Syntactic complexity of bifix-free languages

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)