semi-Thue system


A semi-Thue system 𝔖 is a pair (Ξ£,P) where Ξ£ is an alphabet and P is a non-empty finite binary relationMathworldPlanetmath on Ξ£*, the Kleene star of Ξ£.

Elements of P are variously called defining relations, productions, or rewrite rules, and 𝔖 itself is also known as a rewriting system. If (x,y)∈P, we call x the antecedentPlanetmathPlanetmath, and y the consequent. Instead of writing (x,y)∈P or x⁒P⁒y, we usually write

x→y.

Let 𝔖=(Ξ£,P) be a semi-Thue system. Given a word u over Ξ£, we say that a word v over Ξ£ is immediately derivable from u if there is a defining relation xβ†’y such that

u=r⁒x⁒s   and   v=r⁒y⁒s,

for some words r,s (which may be empty) over Ξ£. If v is immediately derivable from u, we write

u⇒v.

Let Pβ€² be the set of all pairs (u,v)∈Σ*Γ—Ξ£* such that uβ‡’v. Then PβŠ†Pβ€², and

If uβ‡’v, then w⁒uβ‡’w⁒v and u⁒wβ‡’v⁒w for any word w.

Next, take the reflexive transitive closure Pβ€²β€² of Pβ€². Write aβ‡’*b for (a,b)∈Pβ€²β€². So aβ‡’*b means that either a=b, or there is a finite chain a=a1,…,an=b such that aiβ‡’ai+1 for i=1,…,n-1. When aβ‡’*b, we say that b is derivable from a. ConcatenationMathworldPlanetmath preserves derivability:

aβ‡’*b and cβ‡’*d imply a⁒cβ‡’*b⁒d.

Example. Let 𝔖 be a semi-Thue system over the alphabet Ξ£={a,b,c}, with the set of defining relations given by P={abβ†’bc,bcβ†’cb}. Then words a⁒c3⁒b, a2⁒c2⁒b and as b⁒c4 are all derivable from a2⁒b⁒c2:

  • β€’

    a2⁒b⁒c2β‡’a⁒(b⁒c)⁒c2β‡’a⁒c⁒(b⁒c)⁒cβ‡’a⁒c2⁒(c⁒b)=a⁒c3⁒b,

  • β€’

    a2⁒b⁒c2β‡’a2⁒(c⁒b)⁒cβ‡’a2⁒c⁒(c⁒b)=a2⁒c2⁒b, and

  • β€’

    a2⁒b⁒c2β‡’a⁒(b⁒c)⁒c2β‡’(b⁒c)⁒c⁒c2=b⁒c4.

Under 𝔖, we see that if v is derivable from u, then they have the same length: |u|=|v|. Furthermore, if we denote |a|u the number of occurrences of letter a in a word u, then |a|v≀|a|u, |c|vβ‰₯|c|u, and |b|v=|b|u. Also, in order for a word u to have a non-trivial word v (non-trivial in the sense that uβ‰ v) derivable from it, u must have either a⁒b or b⁒c as a subword. Therefore, words like a3 or c3⁒b4⁒a2 have no non-trivial derived words from them.

Remarks.

  1. 1.

    Given a semi-Thue system 𝔖=(Ξ£,P), one can associate a subset A of Ξ£* whose elements we call axioms of 𝔖. Any word v that is derivable from an axiom a∈A is called a theoremMathworldPlanetmath (of 𝔖). If v is a theorem, we write AβŠ’π”–v. The set of all theorems is written L𝔖⁒(A), and is called the languagePlanetmathPlanetmath (over Ξ£) generated by A.

  2. 2.

    Let 𝔖 and A be defined as above, and T any alphabet. Call the elements of T∩Σ the terminals of 𝔖. The set

    L𝔖⁒(A)∩T*

    is called the language generated by A over T, and written L𝔖⁒(A,T). It is easy to see that L𝔖⁒(A,T)=L𝔖⁒(A,T∩Σ).

  3. 3.

    A language L over an alphabet Ξ£ is said to be generable by a semi-Thue system if there is a semi-Thue system 𝔖 and a finite setMathworldPlanetmath of axioms A of 𝔖 such that L=L𝔖⁒(A,Ξ£).

  4. 4.

    Semi-Thue systems are β€œequivalentMathworldPlanetmathPlanetmathPlanetmathPlanetmath” 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β†’y in P into a production S⁒x⁒Tβ†’S⁒y⁒T, where S and T are non-terminals or variablesMathworldPlanetmath. As such, a production of the form S⁒x⁒Tβ†’S⁒y⁒T is sometimes called a semi-Thue production.

  5. 5.

    Given a semi-Thue system 𝔖=(Ξ£,P), the word problem for 𝔖 asks whether or not for any pair of words u,v over Ξ£, one can determine in a finite number of steps (an algorithmMathworldPlanetmath) that uβ‡’*v. If such an algorithm exists, we say that the word problem for 𝔖 is solvable. It turns out there exists a semi-Thue system such that the word problem for it is unsolvable.

  6. 6.

    The word problem for a specific 𝔖 is the same as finding an algorithm to determine whether v is a theorem based on a singleton axiom {u} for arbitrary words u,v.

  7. 7.

    The word problem for semi-Thue systems asks whether or not, given any semi-Thue system 𝔖, the word problem for 𝔖 is solvable. From the previous remark, we see the word problem for semi-Thue systems is unsolvable.

References

  • 1 M. Davis, Computability and Unsolvability. Dover Publications, New York (1982).
  • 2 H. Hermes, Enumerability, Decidability, Computability: An Introduction to the Theory of Recursive FunctionsMathworldPlanetmath. Springer, New York, (1969).
Title semi-Thue system
Canonical name SemiThueSystem
Date of creation 2013-03-22 17:33:16
Last modified on 2013-03-22 17:33:16
Owner CWoo (3771)
Last modified by CWoo (3771)
Numerical id 21
Author CWoo (3771)
Entry type Definition
Classification msc 68Q42
Classification msc 03D40
Classification msc 20M35
Classification msc 03D03
Synonym rewriting rule
Synonym rewrite rule
Synonym rewriting system
Synonym semi-Thue generable
Related topic FormalGrammar
Related topic LabelledStateTransitionSystem
Defines antecedent
Defines consequent
Defines immediately derivable
Defines derivable
Defines defining relation
Defines word problem for semi-Thue systems
Defines semi-Thue production
Defines generable by a semi-Thue system