Namespaces
Variants
Actions

Difference between revisions of "Imbedded word"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (tex encoded by computer)
 
Line 1: Line 1:
 +
<!--
 +
i0501801.png
 +
$#A+1 = 11 n = 0
 +
$#C+1 = 11 : ~/encyclopedia/old_files/data/I050/I.0500180 Imbedded word,
 +
Automatically converted into TeX, above some diagnostics.
 +
Please remove this comment and the {{TEX|auto}} line below,
 +
if TeX found to be correct.
 +
-->
 +
 +
{{TEX|auto}}
 +
{{TEX|done}}
 +
 
''occurrence''
 
''occurrence''
  
A [[Word|word]] of a special type containing complete information about the position of one word inside another. More precisely, an occurrence in an [[Alphabet|alphabet]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050180/i0501801.png" /> is a word of the form <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050180/i0501802.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050180/i0501803.png" /> are words in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050180/i0501804.png" />, while <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050180/i0501805.png" /> is not a letter of that alphabet. The occurrence <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050180/i0501806.png" /> is also an occurrence of the word <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050180/i0501807.png" /> into the word <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050180/i0501808.png" />. The word <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050180/i0501809.png" /> is called the base of this occurrence; the words <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050180/i05018010.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i050/i050180/i05018011.png" /> are known as the left and right wings, respectively. The concept of an occurrence may be made the base of a system of concepts which is convenient for the study of the syntactic structure of words of one type or another.
+
A [[Word|word]] of a special type containing complete information about the position of one word inside another. More precisely, an occurrence in an [[Alphabet|alphabet]] $  A $
 +
is a word of the form $  P \star Q \star R $,  
 +
where $  P, Q, R $
 +
are words in $  A $,  
 +
while $  \star $
 +
is not a letter of that alphabet. The occurrence $  P \star Q \star R $
 +
is also an occurrence of the word $  Q $
 +
into the word $  PQR $.  
 +
The word $  Q $
 +
is called the base of this occurrence; the words $  P $
 +
and $  R $
 +
are known as the left and right wings, respectively. The concept of an occurrence may be made the base of a system of concepts which is convenient for the study of the syntactic structure of words of one type or another.
  
 
====References====
 
====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">  N.M. Nagornyi,  "The theory of algorithms" , Kluwer  (1988)  (Translated from Russian)</TD></TR></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))</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  N.M. Nagornyi,  "The theory of algorithms" , Kluwer  (1988)  (Translated from Russian)</TD></TR></table>
 
 
  
 
====Comments====
 
====Comments====

Latest revision as of 22:11, 5 June 2020


occurrence

A word of a special type containing complete information about the position of one word inside another. More precisely, an occurrence in an alphabet $ A $ is a word of the form $ P \star Q \star R $, where $ P, Q, R $ are words in $ A $, while $ \star $ is not a letter of that alphabet. The occurrence $ P \star Q \star R $ is also an occurrence of the word $ Q $ into the word $ PQR $. The word $ Q $ is called the base of this occurrence; the words $ P $ and $ R $ are known as the left and right wings, respectively. The concept of an occurrence may be made the base of a system of concepts which is convenient for the study of the syntactic structure of words of one type or another.

References

[1] A.A. Markov, "Theory of algorithms" , Israel Program Sci. Transl. (1961) (Translated from Russian) (Also: Trudy Mat. Inst. Steklov. 42 (1954))
[2] N.M. Nagornyi, "The theory of algorithms" , Kluwer (1988) (Translated from Russian)

Comments

The phrase "imbedded word" is not in common use in English. The (English) translation [1] speaks of an entry of one word in another and of left and right delimiters (rather than occurrence, left and right wings, which are used in the (English) translation [2]). Other English-speaking authors tend to refer to an occurrence of one word as a subword (or segment) of another.

References

[a1] S. Eilenberg, "Automata, languages and machines" , A , Acad. Press (1974)
[a2] J.L. Britton, "The word problem" Ann. of Math. , 77 (1963) pp. 16–32
How to Cite This Entry:
Imbedded word. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Imbedded_word&oldid=47314
This article was adapted from an original article by N.M. Nagornyi (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article