Logics for Reversible Regular Languages and Semigroups with Involution

Paul Gastin (1, 2, 3) , Amaldev Manuel (4) , R. Govind (5)

1 LSV - Laboratoire Spécification et Vérification
2 LMF - Laboratoire Méthodes Formelles
3 ReLaX - Research Lab in Computer Science
4 IIT GOA - INDIAN INSTITUTE OF TECHNOLOGY GOA
5 Chennai Mathematical Institute [Inde]

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 operation. The standard connections that exist between MSO and FO logics and varieties of finite semigroups extend to this setting with semigroups extended with an involution. The case is different for FO with neighbour relation where we show that one needs additional equations to characterise the class.

Mots clés: reversible languages; first-order logic; automata; semigroups; Regular languages

Domaines: Informatique [cs]

Paul Gastin, Amaldev Manuel, R. Govind. Logics for Reversible Regular Languages and Semigroups with Involution. Developments in Language Theory (DLT'19), Aug 2019, WARSAW, Poland. pp.182-191, ⟨10.1007/978-3-030-24886-4_13⟩. ⟨hal-04539835⟩