The equivalence and inclusion problems for NTS languages (Q1083219)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | The equivalence and inclusion problems for NTS languages |
scientific article |
Statements
The equivalence and inclusion problems for NTS languages (English)
0 references
1985
0 references
A context-free grammar is said to be NTS if the set of sentential forms it generates is unchanged when the rules are used both ways. We prove that this class of grammars has a decidable equivalence problem. Then we show that one can decide whether a given c.f. grammar is NTS or not. We prove that the class of NTS grammars has an undecidable inclusion problem.
0 references
context-free grammar
0 references
decidable equivalence problem
0 references
NTS grammars
0 references
undecidable inclusion problem
0 references
0 references
