When does partial commutative closure preserve regularity?
International audience The closure of a regular language under commutation or partial commutation has been extensively studied. In this paper, we present new advances on two problems of this area. Problem 1. When is the closure of a regular language under [partial] commutation still regular? Problem...
Main Authors: | , , |
---|---|
Other Authors: | , , , , , , , , |
Format: | Conference Object |
Language: | English |
Published: |
HAL CCSD
2008
|
Subjects: | |
Online Access: | https://hal.science/hal-00340806 https://hal.science/hal-00340806/document https://hal.science/hal-00340806/file/CommutationsWeb.pdf |
id |
ftnormandieuniv:oai:HAL:hal-00340806v1 |
---|---|
record_format |
openpolar |
spelling |
ftnormandieuniv:oai:HAL:hal-00340806v1 2024-04-28T08:26:07+00:00 When does partial commutative closure preserve regularity? Cano Gómez, Antonio Guaiana, Giovanna Pin, Jean-Eric Departamento de Sistemas Informáticos y Computación Valencia Universitat Politècnica de València = Universitad Politecnica de Valencia = Polytechnic University of Valencia (UPV) Laboratoire d'Informatique, de Traitement de l'Information et des Systèmes (LITIS) Université Le Havre Normandie (ULH) Normandie Université (NU)-Normandie Université (NU)-Université de Rouen Normandie (UNIROUEN) Normandie Université (NU)-Institut national des sciences appliquées Rouen Normandie (INSA Rouen Normandie) Institut National des Sciences Appliquées (INSA)-Normandie Université (NU)-Institut National des Sciences Appliquées (INSA) Laboratoire d'informatique Algorithmique : Fondements et Applications (LIAFA) Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS) Reykjavik, Iceland 2008 https://hal.science/hal-00340806 https://hal.science/hal-00340806/document https://hal.science/hal-00340806/file/CommutationsWeb.pdf en eng HAL CCSD Springer Verlag hal-00340806 https://hal.science/hal-00340806 https://hal.science/hal-00340806/document https://hal.science/hal-00340806/file/CommutationsWeb.pdf info:eu-repo/semantics/OpenAccess Proceedings of ICALP 2008 ICALP 2008 https://hal.science/hal-00340806 ICALP 2008, 2008, Reykjavik, Iceland. pp.209-220 [INFO.INFO-OH]Computer Science [cs]/Other [cs.OH] [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM] [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO] [MATH.MATH-GR]Mathematics [math]/Group Theory [math.GR] info:eu-repo/semantics/conferenceObject Conference papers 2008 ftnormandieuniv 2024-04-04T17:28:59Z International audience The closure of a regular language under commutation or partial commutation has been extensively studied. In this paper, we present new advances on two problems of this area. Problem 1. When is the closure of a regular language under [partial] commutation still regular? Problem 2. Are there any robust class of languages closed under [partial] commutation? Let A be a finite alphabet, I a partial commutation on A and D be its complement in A x A. Our main results on Problems 1 and 2 can be summarized as follows: The class Pol G (polynomials of group languages) is closed under commutation. If D is transitive, it is also closed under I-commutation. Under some simple conditions on the graph of I, the closure of a language of Pol G under I-commutation is regular. There is a very robust class of languages W which is closed under commutation. This class, which contains Pol G, is closed under intersection, union, shuffle, concatenation, residual, length preserving morphisms and inverses of morphisms. Further, it is decidable and can be defined as the largest positive variety of languages not containing (ab)*. If I is transitive, the closure of a language of W under I-commutation is regular. The proofs are nontrivial and combine several advanced techniques, including combinatorial Ramsey type arguments, algebraic properties of the syntactic monoid, finiteness conditions on semigroups and properties of insertion systems. Conference Object Iceland Normandie Université: HAL |
institution |
Open Polar |
collection |
Normandie Université: HAL |
op_collection_id |
ftnormandieuniv |
language |
English |
topic |
[INFO.INFO-OH]Computer Science [cs]/Other [cs.OH] [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM] [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO] [MATH.MATH-GR]Mathematics [math]/Group Theory [math.GR] |
spellingShingle |
[INFO.INFO-OH]Computer Science [cs]/Other [cs.OH] [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM] [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO] [MATH.MATH-GR]Mathematics [math]/Group Theory [math.GR] Cano Gómez, Antonio Guaiana, Giovanna Pin, Jean-Eric When does partial commutative closure preserve regularity? |
topic_facet |
[INFO.INFO-OH]Computer Science [cs]/Other [cs.OH] [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM] [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO] [MATH.MATH-GR]Mathematics [math]/Group Theory [math.GR] |
description |
International audience The closure of a regular language under commutation or partial commutation has been extensively studied. In this paper, we present new advances on two problems of this area. Problem 1. When is the closure of a regular language under [partial] commutation still regular? Problem 2. Are there any robust class of languages closed under [partial] commutation? Let A be a finite alphabet, I a partial commutation on A and D be its complement in A x A. Our main results on Problems 1 and 2 can be summarized as follows: The class Pol G (polynomials of group languages) is closed under commutation. If D is transitive, it is also closed under I-commutation. Under some simple conditions on the graph of I, the closure of a language of Pol G under I-commutation is regular. There is a very robust class of languages W which is closed under commutation. This class, which contains Pol G, is closed under intersection, union, shuffle, concatenation, residual, length preserving morphisms and inverses of morphisms. Further, it is decidable and can be defined as the largest positive variety of languages not containing (ab)*. If I is transitive, the closure of a language of W under I-commutation is regular. The proofs are nontrivial and combine several advanced techniques, including combinatorial Ramsey type arguments, algebraic properties of the syntactic monoid, finiteness conditions on semigroups and properties of insertion systems. |
author2 |
Departamento de Sistemas Informáticos y Computación Valencia Universitat Politècnica de València = Universitad Politecnica de Valencia = Polytechnic University of Valencia (UPV) Laboratoire d'Informatique, de Traitement de l'Information et des Systèmes (LITIS) Université Le Havre Normandie (ULH) Normandie Université (NU)-Normandie Université (NU)-Université de Rouen Normandie (UNIROUEN) Normandie Université (NU)-Institut national des sciences appliquées Rouen Normandie (INSA Rouen Normandie) Institut National des Sciences Appliquées (INSA)-Normandie Université (NU)-Institut National des Sciences Appliquées (INSA) Laboratoire d'informatique Algorithmique : Fondements et Applications (LIAFA) Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS) |
format |
Conference Object |
author |
Cano Gómez, Antonio Guaiana, Giovanna Pin, Jean-Eric |
author_facet |
Cano Gómez, Antonio Guaiana, Giovanna Pin, Jean-Eric |
author_sort |
Cano Gómez, Antonio |
title |
When does partial commutative closure preserve regularity? |
title_short |
When does partial commutative closure preserve regularity? |
title_full |
When does partial commutative closure preserve regularity? |
title_fullStr |
When does partial commutative closure preserve regularity? |
title_full_unstemmed |
When does partial commutative closure preserve regularity? |
title_sort |
when does partial commutative closure preserve regularity? |
publisher |
HAL CCSD |
publishDate |
2008 |
url |
https://hal.science/hal-00340806 https://hal.science/hal-00340806/document https://hal.science/hal-00340806/file/CommutationsWeb.pdf |
op_coverage |
Reykjavik, Iceland |
genre |
Iceland |
genre_facet |
Iceland |
op_source |
Proceedings of ICALP 2008 ICALP 2008 https://hal.science/hal-00340806 ICALP 2008, 2008, Reykjavik, Iceland. pp.209-220 |
op_relation |
hal-00340806 https://hal.science/hal-00340806 https://hal.science/hal-00340806/document https://hal.science/hal-00340806/file/CommutationsWeb.pdf |
op_rights |
info:eu-repo/semantics/OpenAccess |
_version_ |
1797585639783268352 |