Classes of languages generated by the Kleene star of a word

Daviaud, Laure; Paperman, Charles

Type de document :

Compte-rendu et recension critique d'ouvrage

DOI :

10.1016/j.ic.2018.07.002

Titre :

Classes of languages generated by the Kleene star of a word

Auteur(s) :

Daviaud, Laure [Auteur]
Faculty of Mathematics, Informatics, and Mechanics [Warsaw] [MIMUW]
Paperman, Charles [Auteur]

Linking Dynamic Data [LINKS]

Titre de la revue :

Information and Computation

Pagination :

90-109

Éditeur :

Elsevier

Date de publication :

2018-10

ISSN :

0890-5401

Mot(s)-clé(s) en anglais :

Automata theory
Regular languages
Profinite equations
Kleene star
Decidability

Discipline(s) HAL :

Informatique [cs]/Informatique et langage [cs.CL]

Résumé en anglais : [en]

In this paper, we study the lattice and the Boolean algebra, possibly closed under quotient, generated by the languages of the form $u⁎$, where $u$ is a word. We provide effective equational characterisations of these ...
Lire la suite >In this paper, we study the lattice and the Boolean algebra, possibly closed under quotient, generated by the languages of the form $u⁎$, where $u$ is a word. We provide effective equational characterisations of these classes, i.e. one can decide using our descriptions whether a given regular language belongs or not to each of them.Lire moins >

Langue :

Anglais

Vulgarisation :

Non

Projet ANR :

Réalisabilité pour la logique classique, la concurrence, les références et la réécriture
Élargir les idées logiques pour l'analyse de complexité

Collections :