Robustness and closure properties of recognizable languages in adhesive categories

• We show that recognizable languages are closed under concatenation by constructing an automaton accepting the concatenation.
• Using counter-examples, we show that recognizable languages are not closed under Kleene-star and substitution.
• We introduce the notion of semi-automata.
• We show that (for suitable categories) semi-automata accept the same class of languages as automata.

We consider recognizable languages of cospans in adhesive categories defined via automaton functors, of which recognizable graph languages are a special case.There are three contributions in this paper: we first show that the notion of recognizable languages is robust in the sense that also semi-functors, i.e., functors that do not necessarily preserve identities, characterize recognizable languages. This is done by converting semi-functors to functors with a procedure akin to epsilon elimination for non-deterministic finite automata.Second, relying on this result, we show that recognizable languages are closed under concatenation, i.e. under cospan composition, by providing a concrete construction that creates a concatenation automaton from two given automata. The construction is considerably more complex than the corresponding construction for finite automata. We conclude by showing negative closure properties for Kleene star and substitution.