RAIRO - Theoretical Informatics and Applications

Table of Contents - July 2001 - Volume 35, Issue 04  

Research Article

Atoms and partial orders of infinite languages

Kuich, Wernera1 and Sauer, N. W.a2

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