Namespaces
Variants
Actions

Difference between revisions of "Word"

From Encyclopedia of Mathematics
Jump to: navigation, search
m (→‎Comments: better)
(reorder)
(4 intermediate revisions by the same user not shown)
Line 1: Line 1:
 
A (linear) sequence of letters (cf. [[Letter]]) from some [[alphabet]]. For example, the series of symbols  "wordinanalphabet"  is a word in any alphabet containing the letters i, w, o, r, d, n, a, l, p, h, b, e, t. For convenience, one also allows the empty word, that is, the word containing no letters. It is a word in any alphabet.
 
A (linear) sequence of letters (cf. [[Letter]]) from some [[alphabet]]. For example, the series of symbols  "wordinanalphabet"  is a word in any alphabet containing the letters i, w, o, r, d, n, a, l, p, h, b, e, t. For convenience, one also allows the empty word, that is, the word containing no letters. It is a word in any alphabet.
  
More precisely, one can use an inductive characterization of a word, whereby the words in an alphabet $A$ are defined as the objects obtained by the following generating process: a) the empty word $\epsilon$ is a word in $A$; b) if an object $P$ is a word in $A$ and $\xi$ is a letter of $A$, then the object $P \xi$ is also a word in $A$. This characterization of words makes it possible to apply inductive arguments in proving universally true statements about the words in a given alphabet.
+
More precisely, one can use an inductive characterization of a word, whereby the words in an alphabet $A$ are defined as the objects obtained by the following generating process: a) the empty word $\epsilon$ is a word in $A$; b) if an object $P$ is a word in $A$ and $\xi$ is a letter of $A$, then the object $P \xi$ is also a word in $A$. This characterization of words makes it possible to apply inductive arguments in proving universally true statements about the words in a given alphabet.  The length of a word is defined inductively: $\ell(\epsilon)=0$, $\ell(P\xi) = \ell(P) + 1$.
  
A word is a fairly general type of [[constructive object]], and because of this, the notion of a word plays an important role in constructive mathematics. The concept of a word is also widely used in algebra, mathematical linguistics and elsewhere.
+
A word is a fairly general type of [[constructive object]], and because of this, the notion of a word plays an important role in constructive mathematics. The concept of a word is also widely used in algebra, mathematical linguistics and elsewhere: in algebra, words normally consist of letters and operation symbols, as  "x+y-z" .
 
 
====References====
 
<table>
 
<TR><TD valign="top">[1]</TD> <TD valign="top">  A.A. Markov,  "Theory of algorithms" , Israel Program Sci. Transl.  (1961)  (Translated from Russian)  (Also: Trudy Mat. Inst. Steklov. 42 (1954))</TD></TR>
 
<TR><TD valign="top">[2]</TD> <TD valign="top">  A.A. Markov,  N.M. [N.M. Nagornyi] Nagorny,  "The theory of algorithms" , Kluwer  (1988)  (Translated from Russian)</TD></TR>
 
</table>
 
 
 
 
 
 
 
====Comments====
 
In algebra, words normally consist of letters and operation symbols, as  "x+y-z" .
 
 
 
The length of a word is defined inductively: $\ell(\epsilon)=0$, $\ell(P\xi) = \ell(P) + 1$.
 
  
 
Under concatenation
 
Under concatenation
Line 23: Line 10:
 
$$
 
$$
 
the set $\Omega(A)$ of all words in an alphabet $A$ becomes an associative [[monoid]]. The empty word is the unit element. This is the [[free monoid]] over $A$. It satisfies the freeness property: For every monoid $M$ and mapping of sets $\phi : A \rightarrow M$ there is a unique morphism of monoids $\tilde\phi : \Omega(A) \rightarrow M$ extending $\phi$. Here, $A$ is identified with the set of words of length $1$ in $\Omega(A)$.
 
the set $\Omega(A)$ of all words in an alphabet $A$ becomes an associative [[monoid]]. The empty word is the unit element. This is the [[free monoid]] over $A$. It satisfies the freeness property: For every monoid $M$ and mapping of sets $\phi : A \rightarrow M$ there is a unique morphism of monoids $\tilde\phi : \Omega(A) \rightarrow M$ extending $\phi$. Here, $A$ is identified with the set of words of length $1$ in $\Omega(A)$.
 
====References====
 
<table>
 
<TR><TD valign="top">[a1]</TD> <TD valign="top">  R.C. Lyndon,  P.E. Schupp,  "Combinatorial group theory" , Springer  (1977)</TD></TR>
 
</table>
 
 
====Comments====
 
 
The notations $A^*$ for the set $\Omega(A)$ of all words over the alphabet $A$ (free monoid) and $A^+$ for the set of all non-empty words over $A$ ([[free semi-group]]) are common.
 
The notations $A^*$ for the set $\Omega(A)$ of all words over the alphabet $A$ (free monoid) and $A^+$ for the set of all non-empty words over $A$ ([[free semi-group]]) are common.
  
 
A '''language''' over $A$ is a set of words over $A$.  See [[Formal language]] and [[Formalized language]].
 
A '''language''' over $A$ is a set of words over $A$.  See [[Formal language]] and [[Formalized language]].
  
An '''infinite word''' over $A$ is a sequence $x_i$ with each $x_i \in A$ indexed by $i$ running over the natural numbers (one-sided) or integers (two-sided, bi-infinite word).
+
An '''infinite word''' over $A$ is a sequence $x_i$ with each $x_i \in A$ indexed by $i$ running over the natural numbers (one-sided, superword) or integers (two-sided, bi-infinite word).
 +
 
 +
A '''factor''' of a word $w = (w_1,w_2,\ldots)$ is a consecutive subsequence of letters $(w_i,w_{i+1},\ldots,w_j)$.
  
 
====References====
 
====References====
 
<table>
 
<table>
 +
<TR><TD valign="top">[1]</TD> <TD valign="top">  A.A. Markov,  "Theory of algorithms" , Israel Program Sci. Transl.  (1961)  (Translated from Russian)  (Also: Trudy Mat. Inst. Steklov. 42 (1954) {{ZBL|0058.00501}})</TD></TR>
 +
<TR><TD valign="top">[2]</TD> <TD valign="top">  A.A. Markov,  N.M. [N.M. Nagornyi] Nagorny,  "The theory of algorithms" , Kluwer  (1988)  (Translated from Russian) {{ZBL|0663.03023}}</TD></TR>
 +
<TR><TD valign="top">[a1]</TD> <TD valign="top">  R.C. Lyndon,  P.E. Schupp,  "Combinatorial group theory" , Ergebnisse der Mathematik und ihrer Grenzgebiete '''89''', Springer  (1977) {{ZBL|0368.20023}}</TD>
 
<TR><TD valign="top">[b1]</TD> <TD valign="top">  Perrin, Dominique; Pin, Jean-Éric, "Infinite words. Automata, semigroups, logic and games", Pure and Applied Mathematics '''141''', Elsevier/Academic Press (2004) ISBN 0-12-532111-2 {{ZBL|1094.68052}}</TD></TR>
 
<TR><TD valign="top">[b1]</TD> <TD valign="top">  Perrin, Dominique; Pin, Jean-Éric, "Infinite words. Automata, semigroups, logic and games", Pure and Applied Mathematics '''141''', Elsevier/Academic Press (2004) ISBN 0-12-532111-2 {{ZBL|1094.68052}}</TD></TR>
 
</table>
 
</table>
 +
 
{{TEX|done}}
 
{{TEX|done}}

Revision as of 21:51, 18 November 2016

A (linear) sequence of letters (cf. Letter) from some alphabet. For example, the series of symbols "wordinanalphabet" is a word in any alphabet containing the letters i, w, o, r, d, n, a, l, p, h, b, e, t. For convenience, one also allows the empty word, that is, the word containing no letters. It is a word in any alphabet.

More precisely, one can use an inductive characterization of a word, whereby the words in an alphabet $A$ are defined as the objects obtained by the following generating process: a) the empty word $\epsilon$ is a word in $A$; b) if an object $P$ is a word in $A$ and $\xi$ is a letter of $A$, then the object $P \xi$ is also a word in $A$. This characterization of words makes it possible to apply inductive arguments in proving universally true statements about the words in a given alphabet. The length of a word is defined inductively: $\ell(\epsilon)=0$, $\ell(P\xi) = \ell(P) + 1$.

A word is a fairly general type of constructive object, and because of this, the notion of a word plays an important role in constructive mathematics. The concept of a word is also widely used in algebra, mathematical linguistics and elsewhere: in algebra, words normally consist of letters and operation symbols, as "x+y-z" .

Under concatenation $$ (a_1 \cdots a_m,b_1 \cdots b_n) \mapsto a_1\cdots a_m b_1 \cdots b_n $$ the set $\Omega(A)$ of all words in an alphabet $A$ becomes an associative monoid. The empty word is the unit element. This is the free monoid over $A$. It satisfies the freeness property: For every monoid $M$ and mapping of sets $\phi : A \rightarrow M$ there is a unique morphism of monoids $\tilde\phi : \Omega(A) \rightarrow M$ extending $\phi$. Here, $A$ is identified with the set of words of length $1$ in $\Omega(A)$. The notations $A^*$ for the set $\Omega(A)$ of all words over the alphabet $A$ (free monoid) and $A^+$ for the set of all non-empty words over $A$ (free semi-group) are common.

A language over $A$ is a set of words over $A$. See Formal language and Formalized language.

An infinite word over $A$ is a sequence $x_i$ with each $x_i \in A$ indexed by $i$ running over the natural numbers (one-sided, superword) or integers (two-sided, bi-infinite word).

A factor of a word $w = (w_1,w_2,\ldots)$ is a consecutive subsequence of letters $(w_i,w_{i+1},\ldots,w_j)$.

References

[1] A.A. Markov, "Theory of algorithms" , Israel Program Sci. Transl. (1961) (Translated from Russian) (Also: Trudy Mat. Inst. Steklov. 42 (1954) Zbl 0058.00501)
[2] A.A. Markov, N.M. [N.M. Nagornyi] Nagorny, "The theory of algorithms" , Kluwer (1988) (Translated from Russian) Zbl 0663.03023
[a1] R.C. Lyndon, P.E. Schupp, "Combinatorial group theory" , Ergebnisse der Mathematik und ihrer Grenzgebiete 89, Springer (1977) Zbl 0368.20023
[b1] Perrin, Dominique; Pin, Jean-Éric, "Infinite words. Automata, semigroups, logic and games", Pure and Applied Mathematics 141, Elsevier/Academic Press (2004) ISBN 0-12-532111-2 Zbl 1094.68052
How to Cite This Entry:
Word. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Word&oldid=36873
This article was adapted from an original article by N.M. Nagornyi (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article