Complexity of certain decision problems about congruential languages (Q1085618): Difference between revisions

In the paper certain decision problems about congruence classes defined by Church-Rosser Thue systems and commutative Thue systems (i.e. rewriting systems over free commutative monoids) are studied. Among other things, it is shown that the question of whether every congruence class defined by a Church-Rosser Thue system is finite, is complete for \(\Pi_ 2\) (a refinement of Jantzen and Monien's construction) while similar question about commutative Thue systems is tractable (an application of Khachian's algorithm).