Topology on Strings

Calude C.S.., J"urgensen, H. and Staiger L

The University of Auckland,
The University of Western Ontario and Universit"at Potsdam,
Martin-Luther-Universit"at Halle-Wittenberg (Halle (Saale))

Abstract:

In this paper we investigate the set of finite and infinite strings, 
$X^{*}$ and $X^{omega}$, over a finite alphabet $X$ as a topological 
space provided with different topologies. As the core of our spaces 
we consider the set of finite strings (words) $X^{*}$, whereas 
the infinite strings of the order type $omega$ (the order type 
of the natural numbers) are seen as limits of finite strings. 

In the past, several topologies on this space have been introduced, 
mainly those which start from the prefix (partial) ordering ''$sqsubseteq$`` 
on the set of finite strings $X^{*}$ and extending it to the whole space 
of finite and infinite words $X^{*}cup X^{omega}$. This yields, 
in some cases, suitable extensions of continuous, that is, 
prefix-preserving mappings of finite words to mappings of infinite words. 

Here we pursue a similar attempt, but we start with partial 
orderings, possibly different from the prefix ordering, 
and the induced right (order) topologies on the set of finite 
words $X^{*}$ and extend them to the whole space of finite and infinite words. 

In particular, we investigate which partial orderings on $X^{*}$ 
yield reasonable extensions. It turns out that prefix-based, 
that is, orderings encompassing the prefix ordering, allow for 
extending the topology from $X^{*}$ to $X^{*}cup X^{omega}$. 
As a further topic of investigation we consider the limits 
generated by the topologies on $X^{*}$ and their 
extensions to $X^{*}cup X^{omega}$. 

In the case of the prefix ordering a crucial r^ole in extending 
continuous, that is, prefix-monotone mappings from the space 
of finite strings $X^{*}$ to the space of finite strings $X^omega$ 
plays the so-called adherence of languages. We give a suitable 
generalisation and a topological interpretation of this notion 
to topologies generated by arbitrary prefix-based partial orderings 
mappings on $X^{*}$ and investigate their relationship to topological limits. 

Finally, we consider the problem of extending monotone w.r.t. 
prefix-based partial orderings mappings on $X^{*}$ to continuous 
mappings on the whole space $X^{*}cup X^{omega}$ via limit and adherence.