Finiteness results on rewriting systems. (English) Zbl 0491.03015


03D03 Thue and Post systems, etc.
03B25 Decidability of theories and sets of sentences
68Q45 Formal languages and automata
68Q65 Abstract data types; algebraic specification
03D05 Automata and formal grammars in connection with logical questions
Full Text: EuDML


[1] 1. N. BOURBAKI, Théorie des Ensembles, Chapt. III, § 6, No. 5, Hermann, Paris, 1963. MR154814 · Zbl 0125.00603
[2] 2. G. HUET, Confluent Reductions: Abstract Properties and Applications to Term Rewriting Systems, in Proceedings of the 18th annual I.E.E.E. Symposium on Fondations of Computer Science, October 1977. MR660480
[3] 3. G. HUET and D. S. LANKFORD, On the Uniform Halting Problem jor Term Rewriting Systems, Rapport de Recherche, No. 283, I.R.I.A., March 1978.
[4] 4. D. E. KNUTH and P. BENDIX, Simple Words Problems in Universal Algebras, in Computational Problems in Abstract Algebras, Ed., J. LEECH, Pergamon Press, 1970, pp. 263-297. Zbl0188.04902 MR255472 · Zbl 0188.04902
[5] 5. D. S. LANKFORD and A. M. BALLANTYNE, The Rejutation Completeness of Blocked Permutative Narrowing and Resolution (to appear).
[6] 6. J. C. RAOULT and J. VUILLEMIN, Operational and Denotational Equivalences Between Recursive Programs, Rapport de Recherche, No. 9, L.R.I., Orsay, June 1978. · Zbl 1282.68165
[7] 7. J. W. THATCHER and J. B. WRIGHT, Generalized Finite Automata Theory with an Application to a Decision Problem of Second Order Logic, Math. System Theory, Vol. 2, 1968, pp. 57-81. Zbl0157.02201 MR224476 · Zbl 0157.02201
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.