On a Conjecture of Schnoebelen

  • Antonio Cano Gómez
  • Jean-Éric Pin
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 2710)


The notion of sequential and parallel decomposition of a language over a set of languages was introduced by Schnoebelen. A language is decomposable if it belongs to a finite set of languages S such that each member of S admits a sequential and parallel decomposition over S. We disprove a conjecture of Schnoebelen concerning decomposable languages and establish some new properties of these languages.


Parallel System Group Language Sequential System Closure Property Rational Language 
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.


Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.


  1. 1.
    J.C.M. Baeten and W.P. Weijland. Process algebra, volume 18 of Cambridge Tract in. Theoretical Computer Science. Cambridge University Press, Cambridge UK, 1990.Google Scholar
  2. 2.
    John H. Conway. Regular Algebra and Finite Machines. Chapman and Hall, London, 1971.zbMATHGoogle Scholar
  3. 3.
    Samuel Eilenberg. Automata, Languages and Machines, volume B. Academic Press, New York, 1976.zbMATHGoogle Scholar
  4. 4.
    Lothaire. Combinatorics on Words, volume 17 of Encyclopedia of Mathematics and. its Applications. aw, reading, 1983.zbMATHGoogle Scholar
  5. 5.
    Jean-Éric Pin. Polynomial closure of group languages and open sets of the hall topology. Theoretical Computer Science, 169:185–200, 1996.zbMATHCrossRefMathSciNetGoogle Scholar
  6. 6.
    Jean-Eric Pin and Pascal Weil. Polynomial closure and unambiguous product. Theory. Comput. Systems, 30:1–39, 1997.CrossRefMathSciNetGoogle Scholar
  7. 7.
    Ph. Schnoebelen. Decomposable regular languages and the shuffle operator. EATCS. Bull., (67):283–289, 1999.Google Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2003

Authors and Affiliations

  • Antonio Cano Gómez
    • 1
  • Jean-Éric Pin
    • 2
  1. 1.Departamento de Sistemas Informáticos y ComputaciónUniversidad Politénica de ValenciaValencia
  2. 2.LIAFAUniversité Paris VII and CNRSParis Cedex 05France

Personalised recommendations