The Regular Languages of Wire Linear AC 0

Authors :: Cadilhac, Michaël
Paperman, Charles
School of Computing [DePaul] (SOC)
DePaul University [Chicago]
Linking Dynamic Data (LINKS)
Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL)
Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Inria Lille - Nord Europe
Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)
Inria Lille - Nord Europe
Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL)
Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)
Publication Year :: 2021
Publisher :: HAL CCSD, 2021.
Abstract: 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.

Subjects :: [INFO.INFO-FL]Computer Science [cs]/Formal Languages and Automata Theory [cs.FL]

Tools