The Regular Languages of Wire Linear AC 0
Document type :
Pré-publication ou Document de travail
Permalink :
Title :
The Regular Languages of Wire Linear AC 0
Author(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]
HAL domain(s) :
Informatique [cs]/Théorie et langage formel [cs.FL]
English abstract : [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 ...
Show more >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.Show less >
Show more >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.Show less >
Language :
Anglais
Collections :
Source :
Submission date :
2021-12-08T02:00:55Z
Files
- https://hal.archives-ouvertes.fr/hal-03466451/document
- Open access
- Access the document