On ground reducibility problem for word rewriting systems with variables

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On ground reducibility problem for word rewriting systems with variables

Full text

Pdf (666 KB)

Source

Symposium on Applied Computing archive
Proceedings of the 1994 ACM symposium on Applied computing table of contents

Phoenix, Arizona, United States

Pages: 271 - 276

Year of Publication: 1994

ISBN:0-89791-647-6

Authors

Gregory Kucherov	INRIA-Lorraine and CRIN, Nancy, France
Michaël Rusinowitch	INRIA-Lorraine and CRIN, Nancy, France

Sponsors

SIGAPL: ACM Special Interest Group on APL Programming Language
SIGCUE: ACM Special Interest Group on Computer Uses In Education
SIGICE: ACM Special Interest Group on Individual Computing Environment
SIGAPP: ACM Special Interest Group on Applied Computing
SIGBIO: ACM Special Interest Group on Biomedical Computing

Publisher

ACM New York, NY, USA

Bibliometrics

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

Additional Information:

references index terms collaborative colleagues

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/326619.326745 What is a DOI?

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	Alfred V. Aho, Algorithms for finding patterns in strings, Handbook of theoretical computer science (vol. A): algorithms and complexity, MIT Press, Cambridge, MA, 1991
	2	D. Angluin. Finding patterns common to a set of strings. Journal of Computer and System Sciences, 21:46-62, 1980.
	3	V. It. J3ean, A. J~hrenleuc.qt, and ~.k'. Mclqulty. Avoidable patterns in strings of symbols. Pacific Journal o/ Mathematics, 85(2):261-294, 1979.
	4	Ronald V. Book, Thue systems as rewriting systems, Journal of Symbolic Computation, v.3 n.1-2, p.39-68, Feb./April 1987 [doi>10.1016/S0747-7171(87)80021-4]
	5	N. Dershowitz and J.-P. Jouannaud. Rewrite ~ysten. s. in J. van Leuven, editor, Handbook o/Theoretical Con,- puter Science. Elsevier Science Publishers }3. V. (North- Holland), 1990.
	6	V.G. Durnev. Positive theory of a free semigroup. Dokl. Akad. Nat& SSSR, 11(4):772-774, 1975. in Russian.
	7	Dieter Hofbauer , Maria Huber, Computing Linearizations Using Test Sets, Proceedings of the Third International Workshop on Conditional Term Rewriting Systems, p.287-301, July 08-10, 1992
	8	Tao Jiang , Arto Salomaa , Kai Salomaa , Sheng Yu, Inclusion is Undecidable for Pattern Languages, Proceedings of the 20th International Colloquium on Automata, Languages and Programming, p.301-312, July 05-09, 1993
	9	j.-P. Jouannaud and E. Kounalis. Proof by induction in equational theories without constructors. In Proceedings 1st IEEE Symposium on Logic in Computer Science, Cambridge (Mass., USA), pages 358-366, t986.
	10	D. Kaput, P. Narendran, D. Rosenkrantz, and H. Zhang. Sufficient-completeness, quasi-reducibility and their complexity. Technical Report 87-27, Dept. of Computer Science, State University of New York at Albany, 1987.
	11	D. Kapur, P. Narendran, and H. Zhang. On sufficient completeness and related properties of term rewriting systems. Acta Informatica, 24'395-415, 1987.
	12	Gregory Kucherov , Mohamed Tajine, Decidability of Regularity and Related Properties of Ground Normal Form Languages, Proceedings of the Third International Workshop on Conditional Term Rewriting Systems, p.272-286, July 08-10, 1992
	13	G. S. Makanin. Algorithmic decidability of the rank of constant free equations in a free semigroup. Dokl. Akad. Nauk. SSSR 243, 243, 1978.
	14	S.S. Marchenko. Undecidability of the positive ~3- theory of a free semigroup. Sibirskii Matematicheskii Zhurnal, 23(1)'196-198, 1982. in Russian.
	15	M. L. Minsky. Recursive unsolvabflity of post's problem of "tag" and other topics in theory of turing machines. Annals of Mathematics, 74(3)'437-455, November 1961.
	16	D. Plaisted. Semantic confluence tests and completion methods. Information and Control, 65'182-215, 1985.
	17	RaM Treinen. A new method for undecidabiilty of first order theories. Technical Report A 09/90, Universit~it des Saarlandes, Fachbereich Informatik, 1990.
	18	S. V~.gv61gyi and R. Gilleron. For a rewriting system it is decidable whether the set of irreducible ground terms is recognizable. Bulletin of European Association for Theoretical Computer Science, 48' 197-209, 1992.