Classes of languages generated by the Kleene star of a word

Autor: Laure Daviaud, Charles Paperman
Přispěvatelé: Faculty of Mathematics, Informatics, and Mechanics [Warsaw] (MIMUW), University of Warsaw (UW), Linking Dynamic Data (LINKS), Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL), Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS), Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL), Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Italiano, G., Pughizzini, G., Sannella, D.
Jazyk: angličtina
Rok vydání: 2018
Předmět:
QA75
Of the form
0102 computer and information sciences
02 engineering and technology
Decidability
Lattice (discrete subgroup)
01 natural sciences
[INFO.INFO-CL]Computer Science [cs]/Computation and Language [cs.CL]
Theoretical Computer Science
QA76
Combinatorics
symbols.namesake
Regular language
Kleene star
ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION
0202 electrical engineering
electronic engineering
information engineering
Profinite equations
0101 mathematics
QA
Quotient
Mathematics
Automata theory
060201 languages & linguistics
Discrete mathematics
Boolean algebra (structure)
010102 general mathematics
Abstract family of languages
Computer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing)
06 humanities and the arts
Regular languages
Computer Science Applications
Computational Theory and Mathematics
010201 computation theory & mathematics
0602 languages and literature
symbols
020201 artificial intelligence & image processing
Word (computer architecture)
Information Systems
Zdroj: Information and Computation
Information and Computation, 2018, 262 (Part 1), pp.90-109. ⟨10.1016/j.ic.2018.07.002⟩
Information and Computation, Elsevier, 2018, 262 (Part 1), pp.90-109. ⟨10.1016/j.ic.2018.07.002⟩
MFCS (1)
Mathematical Foundations of Computer Science 2015 ISBN: 9783662480564
ISSN: 0890-5401
1090-2651
DOI: 10.1016/j.ic.2018.07.002⟩
Popis: International audience; 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.
Databáze: OpenAIRE
Externí odkaz: