Hostname: page-component-cd9895bd7-gxg78 Total loading time: 0 Render date: 2024-12-27T08:41:23.637Z Has data issue: false hasContentIssue false
  • English
  • Français

Atoms and partial orders of infinite languages

Published online by Cambridge University Press:  15 April 2002

Werner Kuich  and
N. W. Sauer
Werner Kuich
Affiliation:
Technische Universität Wien, Wiedner Hauptstraße 8-10, 1040 Wien, Austria; ([email protected])
N. W. Sauer
Affiliation:
University of Calgary, Department of Mathematics and Statistics, 2500 University Dr. NW. Calgary Alberta Canada T2N1N4; ([email protected])
Get access

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.

Keywords

Combinatorics of wordsstructural Ramsey theory.
Type
Research Article
Information
RAIRO - Theoretical Informatics and Applications , Volume 35 , Issue 4 , July 2001 , pp. 389 - 401
Copyright
© EDP Sciences, 2001

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

A. de Luca and St. Varrichio, Finiteness and Regularity in Semigroups and Formal Languages. Springer (1999).
H. Furstenberg, Recurrence in Ergodic Theory and Combinatorial Number Theory. Princeton University Press, Princeton (1981).
Pouzet, M. and Sauer, N., Edge partitions of the Rado graph. Combinatorica 16 (1996) 1-16. CrossRef
F.P. Ramsey, On a problem of formal logic. Proc. London Math. Soc. 30 (1930) 264-286. CrossRef
N. Sauer, Coloring finite substructures of countable structures. The Mathematics of Paul Erdos, X. Bolyai Mathematical Society (to appear).
S. Yu, Regular Languages. In: Handbook of Formal Languages, edited by G. Rozenberg and A. Salomaa, Springer (1997).