Complexity of atoms of regular languages

DOI10.1142/S0129054113400285MaRDI QIDQ5495417zbMATH OpenOpenAlexFDO

Authors Hellis Tamm, Janusz Brzozowski

Publication date 4 August 2014

Published in International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/s0129054113400285

zbMATH Keywords

atomic NFAatomsfinite automatonquotient complexityregular languagestate complexitysyntactic semigroupwitness

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

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

Cites work

• On the state complexity of reversals of regular languages

Cited in

(10)

• Descriptional complexity of regular languages
• Theory of átomata
• Quotient complexities of atoms in regular ideal languages
• Asymptotic approximation for the quotient complexities of atoms
• Unrestricted state complexity of binary operations on regular languages
• Quotient complexities of atoms of regular languages
• Maximally atomic languages
• Theory of átomata
• Most complex non-returning regular languages
• Complexity of left-ideal, suffix-closed and suffix-free regular languages

This page was built for publication: Complexity of atoms of regular languages

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