Thue

Thue

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 regular RBox is a set , where is a regular box of RIAs and is a finite set of role assertions. Since it is undecidable whether a context-free semi-Thue system is regular, we assume that a regular RBox is always accompanied by a mapping that associates each with a finite automaton , which recognizes the words derivable from using the regular semi-Thue system corresponding to . It is called the RIA-automaton-specification of .

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