semi-Thue system

semi-Thue system

The Early Shaping of Cognitive Science by Artificial Intelligence

Published in Alessio Plebe, Pietro Perconti, The Future of the Artificial Mind, 2021

In rewriting systems, the rules, like those in Equation (3.3), have the following general format: αxβ⇒αyβ where α, β are variables in A*, and x,y are fixed words in A*. The combination of all words of an alphabet A and a rewriting systems with rules of the type (3.4) establishes a subset of A*, and is called a semi-Thue system. A compelling question Thue asked for rewriting systems is whether a word w can derive from another word v by applying rewriting rules, for any w, v ∈ A*. About half a century later, Emil Post (1947) gave the answer, demonstrating that this problem is undecidable.

An expressive and tractable rule-based description language

View Article

Journal Information

Published in Enterprise Information Systems, 2019

Linh Anh Nguyen, Ngoc-Thanh Nguyen

A finite set of context-free production rules over is called a context-free semi-Thue system over . It is symmetric if belongs to for every production rule of .3 It is regular if the language consisting of words derivable from any is regular. Assume that is derivable from itself.

Explore chapters and articles related to this topic

The Early Shaping of Cognitive Science by Artificial Intelligence

An expressive and tractable rule-based description language