← All problems
Unverified

Is termination of one linear rule decidable?

The source page states the original problem together with its recorded qualifications and progress updates as follows.

Is termination of one linear (left and right) rule decidable? Left linearity alone is not enough for decidability [Dauchet, 1991].

Recorded progress.

A less ambitious, long-standing open problem (mentioned in [Dauchet, 1991]) is decidability for one (length-increasing) monadic (string, semi-Thue) rule. Termination is undecidable for non-length-increasing monadic systems of rules [Dauchet, 1991]. For one monadic rule, confluence is decidable [Dauchet, 1991]. What about confluence of one non-monadic rule?

Partial results for string rewrite rules have been obtained in [Dauchet, 1991].

The history of the problem and the attempts to solve it are told in [Dauchet, 1991].

Coming soon

Organizer

Boyuan Wang portraitBoyuan Wang
Minghan Wang portraitMinghan Wang
Bochao Li portraitBochao Li
Hongwei Hu portraitHongwei Hu