Quotient complexities of atoms in regular ideal languages

DOI10.14232/ACTACYB.22.2.2015.4zbMATH Open1349.68122arXiv1503.02208OpenAlexW2964038633MaRDI QIDQ2803047FDOQ2803047

Authors: Sylvie Davies, Janusz Brzozowski 

Publication date: 3 May 2016

Published in: Acta Cybernetica (Search for Journal in Brave)

Abstract: A (left) quotient of a language $L$ by a word $w$ is the language $w^{-1}L=xmidwxinL$. The quotient complexity of a regular language $L$ is the number of quotients of $L$; it is equal to the state complexity of $L$, which is the number of states in a minimal deterministic finite automaton accepting $L$. An atom of $L$ is an equivalence class of the relation in which two words are equivalent if for each quotient, they either are both in the quotient or both not in it; hence it is a non-empty intersection of complemented and uncomplemented quotients of $L$. A right (respectively, left and two-sided) ideal is a language $L$ over an alphabet $Sigma$ that satisfies $L=LSigm{a}^{\ast }$ (respectively, $L=Sigm{a}^{\ast }L$ and $L=Sigm{a}^{\ast }LSigm{a}^{\ast }$). We compute the maximal number of atoms and the maximal quotient complexities of atoms of right, left and two-sided regular ideals.

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

Recommendations

• Quotient complexities of atoms of regular languages
• Quotient Complexity of Ideal Languages
• Complexity of atoms of regular languages
• Most complex regular ideal languages
• Quotient complexity of ideal languages

zbMATH Keywords

quotientregular languageatomleft idealright idealstate complexitysyntactic semigrouptwo-sided idealquotient complexity

Mathematics Subject Classification ID

Algebraic theory of languages and automata (68Q70) Semigroups in automata theory, linguistics, etc. (20M35)

Cited In (15)

• Lower bound methods for the size of nondeterministic finite automata revisited
• Most complex non-returning regular languages
• Asymptotic approximation for the quotient complexities of atoms
• Quotient complexity of ideal languages
• Complexity of left-ideal, suffix-closed and suffix-free regular languages
• Quotient Complexity of Ideal Languages
• Complexity of atoms, combinatorially
• Quotients and Atoms of Reversible Languages
• On the computation of quotients and factors of regular languages
• Complexity of atoms of regular languages
• Maximally atomic languages
• Complexity of suffix-free regular languages
• Complexity of suffix-free regular languages
• Most complex regular ideal languages
• Quotient complexities of atoms of regular languages

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

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