  The classical subset construction for non-deterministic automata can be
generalized to other side-effects captured by a monad. The key insight is that
both the state space of the determinized automaton and its
semantics---languages over an alphabet---have a common algebraic structure:
they are Eilenberg-Moore algebras for the powerset monad. In this paper we
study the reverse question to determinization. We will present a construction
to associate succinct automata to languages based on different algebraic
structures. For instance, for classical regular languages the construction will
transform a deterministic automaton into a non-deterministic one, where the
states represent the join-irreducibles of the language accepted by a
(potentially) larger deterministic automaton. Other examples will yield
alternating automata, automata with symmetries, CABA-structured automata, and
weighted automata.
