Syntactic complexity of ideal and closed languages

DOI10.1007/978-3-642-22321-1_11MaRDI QIDQ5199958zbMATH OpenOpenAlexFDO

Authors Yuli Ye, Janusz Brzozowski

Publication date 29 July 2011

Published in Developments in Language Theory (Search for Journal in Brave)

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

zbMATH Keywords

automatonclosedcomplexityideallanguagemonoidregularreversalsemigroupsyntactic

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Abstract: The state complexity of a regular language is the number of states in the minimal deterministic automaton accepting the language. 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 worst-case syntactic complexity taken as a function of the state complexity $n$ of languages in that class. We study the syntactic complexity of the class of regular ideal languages and their complements, the closed languages. We prove that $n^{n-1}$ is a tight upper bound on the complexity of right ideals and prefix-closed languages, and that there exist left ideals and suffix-closed languages of syntactic complexity $n^{n-1}+n-1$, and two-sided ideals and factor-closed languages of syntactic complexity $n^{n-2}+(n-2)2^{n-2}+1$.

Recommendations

• Syntactic complexity of regular ideals
• Upper bounds on syntactic complexity of left and two-sided ideals
• 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

Cited in

(23)

• Quotient complexity of ideal languages
• Syntactic complexity of bifix-free regular languages
• Topological entropy of formal languages
• Syntactic complexity of bifix-free languages
• Complexity of suffix-free regular languages
• Syntactic complexity of \({\mathcal R}\)- and \({\mathcal J}\)-trivial regular languages
• Upper bounds on syntactic complexity of left and two-sided ideals
• Complexity of suffix-free regular languages
• Quotient Complexity of Ideal Languages
• scientific article; zbMATH DE number 140381 (Why is no real title available?)
• Extremal minimality conditions on automata
• Syntactic complexity of prefix-, suffix-, bifix-, and factor-free regular languages
• scientific article; zbMATH DE number 1439073 (Why is no real title available?)
• Syntactic complexity of \(\mathcal{R}\)- and \(\mathcal{J}\)-trivial regular languages
• Syntactic complexity of prefix-, suffix-, and bifix-free regular languages
• Most Complex Regular Right-Ideal Languages
• Upper bound on syntactic complexity of suffix-free languages
• Square on ideal, closed and free languages
• Complexity of left-ideal, suffix-closed and suffix-free regular languages
• Complexity of proper prefix-convex regular languages
• Complexity of proper prefix-convex regular languages
• Binary distinguishability operation
• Syntactic complexity of regular ideals

This page was built for publication: Syntactic complexity of ideal and closed languages

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