Complexity of atoms, combinatorially

DOI10.1016/J.IPL.2016.01.003MaRDI QIDQ5964823zbMATH OpenOpenAlexFDO

Authors Szabolcs Iván

Publication date 1 March 2016

Published in Information Processing Letters (Search for Journal in Brave)

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

zbMATH Keywords

atoms of a languageautomata theoryformal languagesregular languagesyntactic left-congruence classes

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Abstract: Atoms of a (regular) language $L$ were introduced by Brzozowski and Tamm in 2011 as intersections of complemented and uncomplemented quotients of $L$. They derived tight upper bounds on the complexity of atoms in 2013. In 2014, Brzozowski and Davies characterized the regular languages meeting these bounds. To achieve these results, they used the so-called "atomaton" of a language, introduced by Brzozowski and Tamm in 2011. In this note we give an alternative proof of their characterization, via a purely combinatorial approach.

Recommendations

• Parameterized complexity of reconfiguration of atoms
• Asymptotic approximation for the quotient complexities of atoms
• Multiplicative subsets of atoms
• Combinatorics of combinatorial chemistry
• scientific article; zbMATH DE number 1026182
• Fisher-Shannon plane and statistical complexity of atoms
• scientific article; zbMATH DE number 1106524
• Defining statistical relative complexity measure: application to diversity in atoms

Cites work

• Complexity of suffix-free regular languages
• Maximally atomic languages
• Quotient complexities of atoms in regular ideal languages
• Quotient complexities of atoms of regular languages
• Semigroups that contain all singular transformations.
• Theory of átomata

Cited in

(23)

• Descriptional complexity of regular languages
• Yet another canonical nondeterministic automaton
• Quotients and atoms of reversible languages
• Complexity of suffix-free regular 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
• Atoms, gunk, and the limits of `composition'
• Atoms and partial orders of infinite languages
• Maximally atomic languages
• A congruence-based perspective on automata minimization algorithms
• Theory of átomata
• Most complex non-returning regular languages
• Complexity of atoms of regular languages
• The Max-Atom Problem and Its Relevance
• Complexity of left-ideal, suffix-closed and suffix-free regular languages
• Lower bound methods for the size of nondeterministic finite automata revisited
• Complexity of proper prefix-convex regular languages
• Complexity of bifix-free regular languages
• Complexity of proper prefix-convex regular languages
• Complexity of bifix-free regular languages
• Duality of Lattices Associated to Left and Right Quotients
• Yet another canonical nondeterministic automaton

This page was built for publication: Complexity of atoms, combinatorially

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