The equivalence and inclusion problems for NTS languages. (English) Zbl 0604.68086
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.
MSC:
| 68Q45 | Formal languages and automata |
Keywords:
context-free grammar; decidable equivalence problem; NTS grammars; undecidable inclusion problemReferences:
| [1] | Autebert, J. M.; Beauquier, J.; Boasson, L.; Senizergues, G., Remarques sur les langages de parentheses, Theoret. Comput. Sci., 31, 337-349 (1984) · Zbl 0549.68072 |
| [2] | Berstel, J., Congruences plus que parfaites et langages algébriques, (Séminaire d’Informatique Théorique—L.I.T.P. (1975-1977)), 123-147 |
| [3] | Boasson, L., Grammaires a Non-terminaux séparés, (Int. Colloq. Automata. Lang. and Programming. Int. Colloq. Automata. Lang. and Programming, Lecture Notes in Comput. Sci., Vol. 85 (1980), Springer-Verlag: Springer-Verlag Berlin/New York), 109-118 · Zbl 0455.68041 |
| [4] | Boasson, L.; Senizergues, G., N.T.S. languages are congruential and deterministic, J. Comput. System Sci., 31, No. 1 (1985) · Zbl 0604.68087 |
| [5] | Book, R., N.T.S. grammars and Church-Rosser systems, Inform. Process. Lett., 13, 73-76 (1981) · Zbl 0476.68053 |
| [6] | Book, R., Confluent and other types of Thue systems, J. Assoc. Comput. Mach., 29, No. 1, 171-182 (1982) · Zbl 0478.68032 |
| [7] | Butzbach, P., Une famille de congruences de Thue pour laquelle l’équivalence est décidable, (1st Int. Colloq. Automata. Lang. and Programming (1973), North-Holland: North-Holland Amsterdam), 3-12 · Zbl 0274.02012 |
| [8] | Cochet, Y., Sur l’algébricité des classes de certaines congruences définies sur le monoide libre, (Thèse de 3ème cycle (1971), Université de Rennes: Université de Rennes France) |
| [9] | Eilenberg, S., Automata, Languages and Machines (1976), Academic Press: Academic Press New York/London · Zbl 0359.94067 |
| [10] | Frougny, C., Une famille de langages algébriques congruentiels: les langages à Non-terminaux séparés, Thèse de 3ème cycle (1980), Paris |
| [11] | McNaughton, R., Parenthesis grammars, J. Assoc. Comput. Mach., 14, 490-500 (1967) · Zbl 0168.01206 |
| [12] | Nivat, M.; Benois, M., Congruences parfaites et quasi-parfaites, (Séminaire Dubreil (1971-1972)), 25ème année · Zbl 0338.02018 |
| [13] | Nivat, M.; Cochet, Y., Une généralisation des ensembles de Dyck, Israel J. Math., 9, 389-395 (1971) · Zbl 0215.56005 |
| [14] | O’Dunlaing, C., Infinite regular Thue system, Theoret. Comput. Sci., 25, 171-182 (1983) · Zbl 0512.03018 |
| [15] | Oyamaguchi, M.; Inagaki, Y.; Honda, N., The equivalence problem for real-time strict deterministic languages, Inform. and Control, 45, 90-115 (1980) · Zbl 0444.68038 |
| [16] | Senizergues, G., Décidabilité de l’équivalence des grammaires N.T.S., Thèse de 3ème cycle (1981), Paris VII |
| [17] | Takahashi, M., Generalizations of regular sets and their application to a study of context-free languages, Inform. and Control, 27, 1-36 (1975) · Zbl 0291.68031 |
| [18] | Takahashi, M., Nest-sets and relativised closure properties, Theoret. Comput. Sci., 22, 253-264 (1983) · Zbl 0497.68045 |
| [19] | Valiant, L. G., The equivalence problem for deterministic finite-turn pushdown automata, Inform. and Control, 25, 123-133 (1974) · Zbl 0285.68025 |
| [20] | Valiant, L. H.; Paterson, M. S., Deterministic one-counter automata, J. Comput. System Sci., 10, 340-350 (1975) · Zbl 0307.68038 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
