PlanetMath (more info)
 Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
sections
Encyclopædia
Papers
Books
Expositions

meta
Requests (200)
Orphanage
Unclass'd
Unproven (511)
Corrections (9)
Classification

talkback
Polls
Forums
Feedback
Bug Reports

downloads
Snapshots
PM Book

information
News
Docs
Wiki
ChangeLog
TODO List
Legalese
About
Owner confidence rating: Very high Entry average rating: No information on entry rating
semi-Thue system (Definition)

A semi-Thue system $ \mathfrak{S}$ is a pair $ (\Sigma, P)$ where $ \Sigma$ is an alphabet and $ P$ is a non-empty finite binary relation on $ \Sigma^*$, the Kleene star of $ \Sigma$.

Elements of $ P$ are variously called defining relations, productions, or rewrite rules, and $ \mathfrak{S}$ itself is also known as a rewriting system. If $ (x,y)\in P$, we call $ x$ the antecedent, and $ y$ the consequent. Instead of writing $ (x,y)\in P$ or $ xPy$, we usually write

$\displaystyle x\to y.$

Let $ \mathfrak{S}=(\Sigma,P)$ be a semi-Thue system. Given a word $ u$ over $ \Sigma$, we say that a word $ v$ over $ \Sigma$ is immediately derivable from $ u$ if there is a defining relation $ x\to y$ such that

$\displaystyle u=rxs$    and $\displaystyle \qquad v=rys,$
for some words $ r,s$ (which may be empty) over $ \Sigma$. If $ v$ is immediately derivable from $ u$, we write
$\displaystyle u\Rightarrow v.$
Let $ P'$ be the set of all pairs $ (u,v)\in \Sigma^*\times \Sigma^*$ such that $ u\Rightarrow v$. Then $ P\subseteq P'$, and
If $ u\Rightarrow v$, then $ wu\Rightarrow wv$ and $ uw\Rightarrow vw$ for any word $ w$.
Next, take the reflexive transitive closure $ P''$ of $ P'$. Write $ a\stackrel{*}{\Rightarrow}b$ for $ (a,b)\in P''$. So $ a\stackrel{*}{\Rightarrow}b$ means that either $ a=b$, or there is a finite chain $ a=a_1,\ldots,a_n=b$ such that $ a_i\Rightarrow a_{i+1}$ for $ i=1,\ldots,n-1$. When $ a\stackrel{*}{\Rightarrow}b$, we say that $ b$ is derivable from $ a$. Concatenation preserves derivability:
$ a\stackrel{*}{\Rightarrow}b$ and $ c\stackrel{*}{\Rightarrow}d$ imply $ ac\stackrel{*}{\Rightarrow}bd$.

Example. Let $ \mathfrak{S}$ be a semi-Thue system over the alphabet $ \Sigma=\lbrace a,b,c\rbrace$, with the set of defining relations given by $ P=\lbrace ab\to bc, bc \to cb \rbrace$. Then words $ ac^3b$, $ a^2c^2b$ and as $ bc^4$ are all derivable from $ a^2bc^2$:

  • $ a^2bc^2 \Rightarrow a(bc)c^2 \Rightarrow ac(bc)c \Rightarrow ac^2(cb) = ac^3b$,
  • $ a^2bc^2 \Rightarrow a^2(cb)c \Rightarrow a^2c(cb) = a^2c^2b$, and
  • $ a^2bc^2 \Rightarrow a(bc)c^2 \Rightarrow (bc)cc^2 = bc^4$.
Under $ \mathfrak{S}$, we see that if $ v$ is derivable from $ u$, then they have the same length: $ \vert u\vert=\vert v\vert$. Furthermore, if we denote $ \vert a\vert _u$ the number of occurrences of letter $ a$ in a word $ u$, then $ \vert a\vert _v\le \vert a\vert _u$, $ \vert c\vert _v\ge \vert c\vert _u$, and $ \vert b\vert _v = \vert b\vert _u$. Also, in order for a word $ u$ to have a non-trivial word $ v$ (non-trivial in the sense that $ u\ne v$) derivable from it, $ u$ must have either $ ab$ or $ bc$ as a subword. Therefore, words like $ a^3$ or $ c^3b^4a^2$ have no non-trivial derived words from them.

Remarks.

  1. Given a semi-Thue system $ \mathfrak{S}=(\Sigma,P)$, one can associate a subset $ A$ of $ \Sigma^*$ whose elements we call axioms of $ \mathfrak{S}$. Any word $ v$ that is derivable from an axiom $ a\in A$ is called a theorem (of $ \mathfrak{S}$). If $ v$ is a theorem, we write $ A \vdash_{\mathfrak{S}} v$. The set of all theorems is written $ L_{\mathfrak{S}}(A)$, and is called the language (over $ \Sigma$) generated by $ A$.
  2. Let $ \mathfrak{S}$ and $ A$ be defined as above, and $ T$ any alphabet. Call the elements of $ T\cap \Sigma$ the terminals of $ \mathfrak{S}$. The set
    $\displaystyle L_{\mathfrak{S}}(A)\cap T^*$
    is called the language generated by $ A$ over $ T$, and written $ L_{\mathfrak{S}}(A,T)$. It is easy to see that $ L_{\mathfrak{S}}(A,T)=L_{\mathfrak{S}}(A,T\cap \Sigma)$.
  3. A language $ L$ over an alphabet $ \Sigma$ is said to be generable by a semi-Thue system if there is a semi-Thue system $ \mathfrak{S}$ and a finite set of axioms $ A$ of $ \mathfrak{S}$ such that $ L= L_{\mathfrak{S}}(A,\Sigma)$.
  4. Semi-Thue systems are “equivalent” to formal grammars in the following sense:
    a language is generable by a formal grammar iff it is semi-Thue generable.
    The idea is to turn every defining relation $ x\to y$ in $ P$ into a production $ SxT\to SyT$, where $ S$ and $ T$ are non-terminals or variables. As such, a production of the form $ SxT\to SyT$ is sometimes called a semi-Thue production.
  5. Given a semi-Thue system $ \mathfrak{S}=(\Sigma,P)$, the word problem for $ \mathfrak{S}$ asks whether or not for any pair of words $ u,v$ over $ \Sigma$, one can determine in a finite number of steps (an algorithm) that $ u\stackrel{*}{\Rightarrow}v$. If such an algorithm exists, we say that the word problem for $ \mathfrak{S}$ is solvable. It turns out there exists a semi-Thue system such that the word problem for it is unsolvable.
  6. The word problem for a specific $ \mathfrak{S}$ is the same as finding an algorithm to determine whether $ v$ is a theorem based on a singleton axiom $ \lbrace u\rbrace$ for arbitrary words $ u,v$.
  7. The word problem for semi-Thue systems asks whether or not, given any semi-Thue system $ \mathfrak{S}$, the word problem for $ \mathfrak{S}$ is solvable. From the previous remark, we see the word problem for semi-Thue systems is unsolvable.

Bibliography

1
M. Davis, Computability and Unsolvability. Dover Publications, New York (1982).
2
H. Hermes, Enumerability, Decidability, Computability: An Introduction to the Theory of Recursive Functions. Springer, New York, (1969).



"semi-Thue system" is owned by CWoo.
(view preamble)

View style:

See Also: formal grammar

Other names:  rewriting rule, rewrite rule, rewriting system, semi-Thue generable
Also defines:  antecedent, consequent, immediately derivable, derivable, defining relation, word problem for semi-Thue systems, semi-Thue production, generable by a semi-Thue system

Attachments:
Thue system (Definition) by CWoo
Log in to rate this entry.
(view current ratings)

Cross-references: singleton, solvable, algorithm, word problem, variables, non-terminals, iff, generable by a formal grammar, formal grammars, finite set, easy to see, terminals, generated by, language, axioms, subset, associate, subword, order, occurrences, number, length, imply, preserves, concatenation, finite chain, reflexive transitive closure, word, productions, Kleene star, binary relation, finite, alphabet
There are 21 references to this entry.

This is version 17 of semi-Thue system, born on 2007-09-24, modified 2008-02-14.
Object id is 9960, canonical name is SemiThueSystem.
Accessed 3170 times total.

Classification:
AMS MSC: 03D03 (Mathematical logic and foundations :: Computability and recursion theory :: Thue and Post systems, etc.)
 20M35 (Group theory and generalizations :: Semigroups :: Semigroups in automata theory, linguistics, etc.)
 03D40 (Mathematical logic and foundations :: Computability and recursion theory :: Word problems, etc.)
 68Q42 (Computer science :: Theory of computing :: Grammars and rewriting systems)
Pending Errata and Addenda
None.
Discussion
Style: Expand: Order:
forum policy

No messages.

Interact
post | correct | update request | add derivation | add example | add (any)