Thue systems

Thue systems
Name	Thue systems
Caption	String rewriting schematic
Field	Mathematics; Theoretical computer science
Introduced	1914
Introduced by	Axel Thue
Related	Combinatorics on words, Term rewriting system, Semi-Thue system, Group theory

Thue systems Thue systems are formal string-rewriting mechanisms introduced in the early 20th century for studying equivalence of words under replacement rules. They provide a minimal, abstract framework used in investigations across Mathematics and Theoretical computer science, linking combinatorial questions about sequences with algorithmic problems such as the word problem for algebraic structures. Thue systems serve as prototypes for more structured frameworks like Term rewriting systems, and they underpin undecidability results connected with figures and institutions such as Emil Post and Alan Turing.

Definition and Formalism

A Thue system is a pair (Σ, R) where Σ is a finite alphabet and R is a set of unordered pairs of nonempty words over Σ called rewriting rules. Formal definitions deploy notions from Formal language theory and Automata theory: if (u, v) ∈ R then u may be replaced by v and v by u inside any context, generating the symmetric, reflexive, transitive closure called Thue congruence. The central object is the congruence relation ≡R on Σ* generated by R; equivalently, ≡R is the smallest congruence containing each pair (u, v). Terms from Combinatorics on words, such as factors, prefixes, and morphisms, appear naturally in formal statements. Connections to algebraic structures arise by viewing the quotient monoid Σ*/≡R as a presented monoid or semigroup, analogous to presentations used in Group theory and Semigroup theory.

Examples and Basic Properties

Basic examples illustrate how Thue systems encode algebraic and combinatorial phenomena. A finite confluent Thue system yields a canonical form for each equivalence class, an idea paralleled in Knuth–Bendix completion contexts. Classic illustrative rules include commutation rules like ab ↔ ba, which model abelianization processes akin to presentations of Free abelian groups when further group axioms are imposed. Other examples encode the relations of well-known algebraic objects such as presentations of finite semigroups arising in studies by Adjan and Bergman. Structural properties consider normal forms, critical pairs, overlaps, and Church–Rosser properties; these notions relate to theorems proved in the tradition of Noether, Hilbert, and algorithmic developments by Knuth and Bendix.

Word Problem and Undecidability

The word problem for Thue systems asks whether two given words are equivalent under ≡R. This decision problem played a crucial role in the development of computability theory: Adyan, Novikov, and others established undecidability results for group and semigroup word problems, building on techniques that relate Thue systems to Turing computation. The undecidability of the general word problem for Thue systems mirrors seminal results by Emil Post on production systems and by Alan Turing on the Entscheidungsproblem. Specific constructions reduce the halting problem for machines like Turing machines and models such as Post correspondence problem instances to equivalence questions in particular Thue systems, demonstrating that no algorithm can decide equivalence in full generality. Contrastingly, subclasses with constraints on rules or alphabets yield decidable cases studied by researchers including Matiyasevich and Higman.

Connections to Rewriting Systems and Semigroup Theory

Thue systems are historically and formally close to semi-Thue systems and modern term rewriting systems: they can be viewed as zero-arity term rewriting systems or as presentations of monoids and semigroups via relations. This perspective situates Thue systems within the lineage connecting Combinatorial group theory techniques, Rewriting theory frameworks, and computational treatments pioneered by the likes of Newman and Knuth–Bendix. In semigroup theory, presentations by generators and relations often employ Thue-style relations to study growth, amenability, and decidability, intersecting with work by Adian, Varopoulos, and Gromov on group growth and geometric connections. Interplays arise with Automatic groups and Rewriting automata where finite-state devices capture restricted Thue congruences; papers by Hopcroft, Ullman, and Ehrenfeucht analyze algorithmic aspects.

Complexity and Decision Problems

Beyond undecidability, quantitative complexity questions concern the difficulty of deciding reachability, membership, normal form computation, and equivalence in constrained Thue systems. For various restricted classes, decision problems lie in complexity classes such as P, NP, PSPACE, and EXPSPACE; reductions often use classic sources like Cook and Karp for NP-hardness or harness space-bounded machine simulations to prove PSPACE-completeness. The computational cost of computing normal forms or confluence certificates connects with algorithmic paradigms in Graph theory and Formal verification, and hardness results sometimes invoke combinatorial constructions related to Post and Rabin frameworks. Research continues into parameterized complexity and approximation for constrained rewriting settings explored by scholars connected to SIAM and ACM conferences.

Historical Development and Applications

Thue systems originate with Axel Thue's early 20th-century investigations into word combinatorics and Diophantine approximation. Subsequent decades saw integration with computability milestones by Post and Turing, and with algebraic developments by Novikov, Adyan, and Higman that shaped modern combinatorial and algorithmic algebra. Applications span decision procedures in Computer algebra systems, foundations of Formal verification, modeling in Symbolic dynamics, and encoding problems in Cryptography and Coding theory where string transformations matter. Contemporary work links Thue-style rewriting to categorical and homological methods used by communities around institutions like Institute for Advanced Study and conferences such as those organized by European Association for Theoretical Computer Science.

Category:String rewriting systems