Classes of languages generated by the Kleene star of a word

Daviaud, Laure; Paperman, Charles

Document type :

Compte-rendu et recension critique d'ouvrage

DOI :

10.1016/j.ic.2018.07.002

Title :

Classes of languages generated by the Kleene star of a word

Author(s) :

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

Linking Dynamic Data [LINKS]

Journal title :

Information and Computation

Pages :

90-109

Publisher :

Elsevier

Publication date :

2018-10

ISSN :

0890-5401

English keyword(s) :

Automata theory
Regular languages
Profinite equations
Kleene star
Decidability

HAL domain(s) :

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

English abstract : [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 ...
Show more >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.Show less >

Language :

Anglais

Popular science :

Non

ANR Project :

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 :