Recognizability of zigzag languages and stack languages. (English) Zbl 0923.68082

Almeida, Jorge (ed.) et al., Semigroups, automata and languages. Papers from the conference, Porto, Portugal, June 20–24, 1994. Singapore: World Scientific. 153-166 (1996).
Summary: We study two extensions of the concatenation: the zigzag operation and the \(\sharp\)-operation. We propose two definitions of recognizability associated with these operations and we prove their equivalence with the notions of \(z\)-language and \(\sharp\)-language. We also, study the case where the recognizability is made by a finite monoid. In particular, we show that the languages \(\sharp\)-recognized by finite monoids are exactly the set of rational \(\sharp\)-languages described by reversible minimal and deterministic automata and whose prefix sets are submonoids. Concerning \(z\)-languages, the finite case is still open.
For the entire collection see [Zbl 0905.00053].


68Q45 Formal languages and automata