Logics for Reversible Regular Languages and Semigroups with Involution

Paul Gastin, Amaldev Manuel, R. Govind

We present MSO and FO logics with predicates `between' and `neighbour' that characterise various fragments of the class of regular languages that are closed under the reverse opera…