Arrow Research search

Author name cluster

Antonio Cano

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

2 papers
1 author row

Possible papers

2

I&C Journal 2013 Journal Article

Regular languages and partial commutations

  • Antonio Cano
  • Giovanna Guaiana
  • Jean-Éric Pin

The closure of a regular language under a [partial] commutation I has been extensively studied. We present new advances on two problems of this area: (1) When is the closure of a regular language under [partial] commutation still regular? (2) Are there any robust classes of languages closed under [partial] commutation? We show that the class Pol ( G ) of polynomials of group languages is closed under commutation, and under partial commutation when the complement of I in A 2 is a transitive relation. We also give a sufficient graph theoretic condition on I to ensure that the closure of a language of Pol ( G ) under I-commutation is regular. We exhibit a very robust class of languages W which is closed under commutation. This class contains Pol ( G ), is decidable and can be defined as the largest positive variety of languages not containing ( a b ) ⁎. It is also closed under intersection, union, shuffle, concatenation, quotients, length-decreasing morphisms and inverses of morphisms. If I is transitive, we show that 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.

Details DOI

TCS Journal 2009 Journal Article

On locally reversible languages

  • Pedro García
  • Manuel Vázquez de Parga
  • Antonio Cano
  • Damián López

There exist several works that study the class of reversible languages defined as the union closure of 0-reversible languages, their properties and suitable representations. In this work we define and study the class of locally reversible languages, defined as the union closure of k -reversible languages. We characterize the class and prove that it is a local (positive) variety of formal languages. We also extend the definition of quasi-reversible automata to deal with locally reversible languages and propose a polynomial algorithm to obtain, for any given locally k -reversible language, a quasi- k -reversible automaton.

Details DOI
v2026.09.13