Classes of languages generated by the Kleene star of a word

Laure Daviaud; Charles Paperman

doi:10.1016/j.ic.2018.07.002

Classes of languages generated by the Kleene star of a word

Laure Daviaud, Charles Paperman

School of Computing Sciences

Research output: Contribution to journal › Article › peer-review

Abstract

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.

Original language	English
Pages (from-to)	90-109
Number of pages	20
Journal	Information and Computation
Volume	262
Early online date	26 Sep 2018
DOIs	https://doi.org/10.1016/j.ic.2018.07.002
Publication status	Published - Oct 2018

Keywords

Automata theory
Decidability
Kleene star
Profinite equations
Regular languages

Access to Document

10.1016/j.ic.2018.07.002Licence: Other

https://openaccess.city.ac.uk/id/eprint/21287Licence: CC BY-NC-ND

Cite this

@article{ab9e688ba13a4fd596ed6f3b0c1cb95f,

title = "Classes of languages generated by the Kleene star of a word",

abstract = "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.",

keywords = "Automata theory, Decidability, Kleene star, Profinite equations, Regular languages",

author = "Laure Daviaud and Charles Paperman",

note = "Funding Information: This work was carried out when the first author was supported by ANR Project ELICA ANR-14-CE25-0005 and by ANR Project RECRE ANR-11-BS02-0010 (ENS Lyon, France) and the second author by Warsaw Center of Mathematics and Computer Science (WCMCS) (Poland). ",

year = "2018",

month = oct,

doi = "10.1016/j.ic.2018.07.002",

language = "English",

volume = "262",

pages = "90--109",

journal = "Information and Computation",

issn = "0890-5401",

publisher = "Elsevier",

}

TY - JOUR

T1 - Classes of languages generated by the Kleene star of a word

AU - Daviaud, Laure

AU - Paperman, Charles

N1 - Funding Information: This work was carried out when the first author was supported by ANR Project ELICA ANR-14-CE25-0005 and by ANR Project RECRE ANR-11-BS02-0010 (ENS Lyon, France) and the second author by Warsaw Center of Mathematics and Computer Science (WCMCS) (Poland).

PY - 2018/10

Y1 - 2018/10

N2 - 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.

AB - 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.

KW - Automata theory

KW - Decidability

KW - Kleene star

KW - Profinite equations

KW - Regular languages

UR - http://www.scopus.com/inward/record.url?scp=85050085566&partnerID=8YFLogxK

U2 - 10.1016/j.ic.2018.07.002

DO - 10.1016/j.ic.2018.07.002

M3 - Article

AN - SCOPUS:85050085566

VL - 262

SP - 90

EP - 109

JO - Information and Computation

JF - Information and Computation

SN - 0890-5401

ER -

Classes of languages generated by the Kleene star of a word

Abstract

Keywords

Access to Document

Other files and links

Cite this