Large Aperiodic Semigroups

DOI10.1007/978-3-319-08846-4_9zbMATH Open1302.68154arXiv1401.0157OpenAlexW1526344047MaRDI QIDQ3192257FDOQ3192257

Authors: Marek Szykuła, Janusz Brzozowski 

Publication date: 26 September 2014

Published in: Implementation and Application of Automata (Search for Journal in Brave)

Abstract: The syntactic complexity of a regular language is the size of its syntactic semigroup. This semigroup is isomorphic to the transition semigroup of the minimal deterministic finite automaton accepting the language, that is, to the semigroup generated by transformations induced by non-empty words on the set of states of the automaton. In this paper we search for the largest syntactic semigroup of a star-free language having $n$ left quotients; equivalently, we look for the largest transition semigroup of an aperiodic finite automaton with $n$ states. We introduce two new aperiodic transition semigroups. The first is generated by transformations that change only one state; we call such transformations and resulting semigroups unitary. In particular, we study complete unitary semigroups which have a special structure, and we show that each maximal unitary semigroup is complete. For $nge4$ there exists a complete unitary semigroup that is larger than any aperiodic semigroup known to date. We then present even larger aperiodic semigroups, generated by transformations that map a non-empty subset of states to a single state; we call such transformations and semigroups semiconstant. In particular, we examine semiconstant tree semigroups which have a structure based on full binary trees. The semiconstant tree semigroups are at present the best candidates for largest aperiodic semigroups. We also prove that $2^n-1$ is an upper bound on the state complexity of reversal of star-free languages, and resolve an open problem about a special case of state complexity of concatenation of star-free languages.

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

Recommendations

• Large aperiodic semigroups
• Almost disjoint large subsets of semigroups
• scientific article; zbMATH DE number 1532123
• Iterated periodicity over finite aperiodic semigroups
• scientific article; zbMATH DE number 4109021
• Structure Results for Transitive, Untwisted, Superlinked Finite Covers
• Semilattice indecomposable finite semigroups with large subsemilattices
• Periods of strongly continuous semigroups
• Finite aperiodic semigroups with commuting idempotents and generalizations
• Large semigroups of cellular automata.

zbMATH Keywords

unitarytransition semigroupaperiodicsyntactic complexitymonotonicstar-free languagepartially monotonicsemiconstantnearly monotonic

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Semigroups in automata theory, linguistics, etc. (20M35)

Cited In (4)

• Semiregular large sets
• Checking whether an automaton is monotonic is NP-complete
• Large aperiodic semigroups
• Descriptional complexity of regular languages

This page was built for publication: Large Aperiodic Semigroups

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