The Regular Languages of Wire Linear AC 0
Type de document :
Pré-publication ou Document de travail
URL permanente :
Titre :
The Regular Languages of Wire Linear AC 0
Auteur(s) :
Cadilhac, Michaël [Auteur]
School of Computing [DePaul] [SOC]
Paperman, Charles [Auteur]
Linking Dynamic Data [LINKS]
School of Computing [DePaul] [SOC]
Paperman, Charles [Auteur]
Linking Dynamic Data [LINKS]
Discipline(s) HAL :
Informatique [cs]/Théorie et langage formel [cs.FL]
Résumé en anglais : [en]
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 ...
Lire la suite >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.Lire moins >
Lire la suite >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.Lire moins >
Langue :
Anglais
Collections :
Source :
Date de dépôt :
2021-12-08T02:00:55Z
Fichiers
- https://hal.archives-ouvertes.fr/hal-03466451/document
- Accès libre
- Accéder au document