Complexity of certain decision problems about congruential languages (Q1085618): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
| Property / full work available at URL | |||
| Property / full work available at URL: https://doi.org/10.1016/0022-0000(85)90051-0 / rank | |||
Normal rank | |||
| Property / OpenAlex ID | |||
| Property / OpenAlex ID: W2058954424 / rank | |||
Normal rank | |||
Revision as of 22:47, 19 March 2024
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Complexity of certain decision problems about congruential languages |
scientific article |
Statements
Complexity of certain decision problems about congruential languages (English)
0 references
1985
0 references
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).
0 references
congruential language
0 references
congruence classes
0 references
Church-Rosser Thue systems
0 references
commutative Thue systems
0 references
rewriting systems
0 references
