Syntactic complexities of some classes of star-free languages

DOI10.1007/978-3-642-31623-4_9MaRDI QIDQ3167576zbMATH OpenOpenAlexFDO

Authors Baiyu Li, Janusz Brzozowski

Publication date 2 November 2012

Published in Descriptional Complexity of Formal Systems (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1109.3381, http://hdl.handle.net/10012/12508

zbMATH Keywords

finite automatonmonotonicnearly monotonicpartially monotonicstar-free languagesyntactic complexitysyntactic semigroup

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Abstract: The syntactic complexity of a regular language is the cardinality of its syntactic semigroup. The syntactic complexity of a subclass of regular languages is the maximal syntactic complexity of languages in that subclass, taken as a function of the state complexity of these languages. We study the syntactic complexity of star-free regular languages, that is, languages that can be constructed from finite languages using union, complement and concatenation. We find tight upper bounds on the syntactic complexity of languages accepted by monotonic and partially monotonic automata. We introduce "nearly monotonic" automata, which accept star-free languages, and find a tight upper bound on the syntactic complexity of languages accepted by such automata. We conjecture that this bound is also an upper bound on the syntactic complexity of star-free languages.

Recommendations

• Syntactic complexities of six classes of star-free languages
• Syntactic complexity of prefix-, suffix-, and bifix-free regular languages
• Syntactic complexity of prefix-, suffix-, bifix-, and factor-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

(10)

• On syntactic complexity of circular semi-flower automata
• Syntactic complexity of suffix-free languages
• The syntactic complexity of semi-flower languages
• Syntactic complexity of \({\mathcal R}\)- and \({\mathcal J}\)-trivial regular 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
• Syntactic complexity of \(\mathcal{R}\)- and \(\mathcal{J}\)-trivial regular languages
• Syntactic complexities of six classes of star-free languages
• Syntactic complexity of prefix-, suffix-, and bifix-free regular languages

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

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