Quotient complexities of atoms of regular languages

DOI10.1007/978-3-642-31653-1_6MaRDI QIDQ3167483zbMATH OpenOpenAlexFDO

Authors Hellis Tamm, Janusz Brzozowski

Publication date 2 November 2012

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

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

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Abstract: An atom of a regular language L with n (left) quotients is a non-empty intersection of uncomplemented or complemented quotients of L, where each of the n quotients appears in a term of the intersection. The quotient complexity of L, which is the same as the state complexity of L, is the number of quotients of L. We prove that, for any language L with quotient complexity n, the quotient complexity of any atom of L with r complemented quotients has an upper bound of 2^n-1 if r=0 or r=n, and 1+sum_{k=1}^{r} sum_{h=k+1}^{k+n-r} C_{h}^{n} cdot C_{k}^{h} otherwise, where C_j^i is the binomial coefficient. For each nge 1, we exhibit a language whose atoms meet these bounds.

Recommendations

• Complexity of atoms of regular languages
• Quotient complexities of atoms in regular ideal languages
• Complexity of atoms, combinatorially
• Asymptotic approximation for the quotient complexities of atoms
• Maximally atomic languages

Cited in

(7)

• Quotient complexities of atoms in regular ideal languages
• Asymptotic approximation for the quotient complexities of atoms
• On the computation of quotients and factors of regular languages
• Maximally atomic languages
• Complexity of atoms of regular languages
• Complexity of atoms, combinatorially
• Quotients and Atoms of Reversible Languages

This page was built for publication: Quotient complexities of atoms of regular languages

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