On some families of languages related to the Dyck language

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On some families of languages related to the Dyck language

Full text

Pdf (247 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the second annual ACM symposium on Theory of computing table of contents

Northampton, Massachusetts, United States

Pages: 221 - 225

Year of Publication: 1970

Author

Maurice Nivat

Professior, Faculté des Sciences de Paris, France

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 0, Downloads (12 Months): 13, Citation Count: 4

Additional Information:

abstract references cited by index terms

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/800161.805168 What is a DOI?

ABSTRACT

We recall that the Dyck language on the alphabet of 2n letters X &equil; {x1,...,xn,&xmarc;1,...,&xmarc;n} is the equivalence class of the empty word 1 &egr; X@@@@ modulo the Thue congruence generated on X@@@@ by the 2n relations xi&xmarc;i &equil; &xmarc;ixi &equil; 1 i &egr; {1,...,n}. Indeed for all n &egr; X@@@@ the equivalence class of n modulo this congruence is a non ambiguous algebraic (ie. context-free) language, the complement of which is also a non ambiguous algebraic language. The same situation is true for the congruence generated on X@@@@ by the n relations xi&xmarc;i &equil; 1 i &egr; {1,...,n}. The author convinced himself that many other congruences have the same property [Ni 1], and undertook the task of finding them systematically. Here is presented a part of the results of this undertaking. An important family of congruences is brought to light which have interesting decidability properties: in the constructions leading to these decidability properties we used as a guide line the nice paper of Mac Naughton [McN]. Sufficient conditions are given in order that the equivalence classes (and their complements) of such a congruence be an algebraic language. We do not study in this paper the properties of these languages, this will be done elsewhere [Ni 2].

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Robert McNaughton, Parenthesis Grammars, Journal of the ACM (JACM), v.14 n.3, p.490-500, July 1967 [doi>10.1145/321406.321411]
	2	Maurice Nivat - Congruences de Thue et t-langages. To appear in Acta Scientiarum Mathematicarum Hungaricae.
	3	Maurice Nivat et Yves Cochet - Une généralisation des ensembles de Dyck. Submitted for publication in Israel Journal of Math.

CITED BY 4

	Gérard Huet, Confluent Reductions: Abstract Properties and Applications to Term Rewriting Systems: Abstract Properties and Applications to Term Rewriting Systems, Journal of the ACM (JACM), v.27 n.4, p.797-821, Oct. 1980
	Ronald V. Book, Confluent and Other Types of Thue Systems, Journal of the ACM (JACM), v.29 n.1, p.171-182, Jan. 1982
	Ravi Sethi, Errata: `` Testing for the Church-Rosser Property'', Journal of the ACM (JACM), v.22 n.3, p.424, July 1975
	Rémi Eyraud , Colin Higuera , Jean-Christophe Janodet, LARS: A learning algorithm for rewriting systems, Machine Learning, v.66 n.1, p.7-31, January 2007