PlanetMath: alternative treatment of concatenation

(more info)

Math for the people, by the people.

Main Menu

sections Encyclopædia
Papers
Books
Expositions

meta Requests (200)
Orphanage
Unclass'd
Unproven (490)
Corrections (6)
Classification

talkback Polls
Forums
Feedback
Bug Reports

downloads Snapshots
PM Book

information News
Docs
Wiki
ChangeLog
TODO List
Legalese
About

alternative treatment of concatenation

(Definition)

It is possible to define words and concatenation in terms of ordered sets. Let be a set, which we shall call our alphabet. Define a word on to be a map from a totally ordered set into . (In order to have words in the usual sense, the ordered set should be finite but, as the definition presented here does not require this condition, we do not impose it.)

Suppose that we have totally ordered sets and $(v,\prec)$ and words $f \colon u \to A$ and $g \colon v \to A$ . Let $u \coprod v$ denote the disjoint union of and and let $p \colon u \to u \coprod v$ and $q \colon u \to u \coprod v$ be the canonical maps. Then we may define an order $\ll$ on $u \coprod v$ as follows:

If $x \in u$ and $y \in u$ , then $p(x) \ll p(y)$ if and only if .
If $x \in u$ and $y \in v$ , then $p(x) \ll q(y)$ .
If $x \in v$ and $y \in v$ , then $q(x) \ll q(y)$ if and only if $x \prec y$ .

We define the concatenation of

and

, which will be denoted $f \circ g$ , to be map from $u \coprod v$ to

defined by the following conditions:

If $x \in u$ , then $(f \circ g) (p(x)) = f(x)$ .
If $y \in u$ , then $(f \circ g) (q(x)) = g(x)$ .

"alternative treatment of concatenation" is owned by rspuzio. [ full author list (2) ]

(view preamble)

See Also: word

This object's parent.

Log in to rate this entry.
(view current ratings)

Cross-references: canonical, disjoint union, finite, order, totally ordered set, map, alphabet, terms, concatenation, words
There is 1 reference to this entry.

This is version 3 of alternative treatment of concatenation, born on 2007-07-17, modified 2007-11-11.
Object id is 9774, canonical name is AlternativeTreatmentOfConcatenation.
Accessed 382 times total.

Classification:

AMS MSC:	68Q70 (Computer science :: Theory of computing :: Algebraic theory of languages and automata)
	20M35 (Group theory and generalizations :: Semigroups :: Semigroups in automata theory, linguistics, etc.)

Pending Errata and Addenda

None.[ View all 1 ]

Discussion

forum policy

No messages.

Interact