The Regular Languages of Wire Linear AC 0

Michaël Cadilhac (1) , Charles Paperman (2)

1 SOC - School of Computing [DePaul]
2 LINKS - Linking Dynamic Data

In this paper, the regular languages of wire linear AC 0 are characterized as the languages expressible in the two-variable fragment of first-order logic with regular predicates, FO 2 [reg]. Additionally, they are characterized as the languages recognized by the algebraic class QLDA. The class is shown to be decidable and examples of languages in and outside of it are presented.

Domaines: Théorie et langage formel [cs.FL]

Michaël Cadilhac, Charles Paperman. The Regular Languages of Wire Linear AC 0. 2021. ⟨hal-03466451v2⟩