RAIRO - Theoretical Informatics and Applications

Research Article

Atoms and partial orders of infinite languages

Werner Kuicha1 and N. W. Sauera2

a1 Technische Universität Wien, Wiedner Hauptstraße 8-10, 1040 Wien, Austria; (kuich@tuwien.ac.at)

a2 University of Calgary, Department of Mathematics and Statistics, 2500 University Dr. NW. Calgary Alberta Canada T2N1N4; (nsauer@math.ucalgary.ca)

Abstract

We determine minimal elements, i.e., atoms, in certain partial orders of factor closed languages under . This is in analogy to structural Ramsey theory which determines minimal structures in partial orders under embedding.

(Received February 1 2001)

(Accepted September 27 2001)

(Online publication April 15 2002)

Key Words:

  • Combinatorics of words;
  • structural Ramsey theory.

Mathematics Subject Classification:

  • 68R15;
  • 05C55
Metrics