Name: THE WORD PROBLEM OF ACD-GROUND THEORIES IS UNDECIDABLE
Creator: Marché, Claude
Keywords: Decidability of theories and sets of sentences, Word problems (aspects of algebraic structures), Grammars and rewriting systems, 0102 computer and information sciences, 0101 mathematics, Word problems, etc. in computability and recursion theory, 01 natural sciences, equational theory, ground equations

The word problem of ACD-ground theories is undecidable

descriptionPublicationkeyboard_double_arrow_right Article 01 Mar 1992 English Publisher:World Scientific Pub Co Pte LtJournal:International Journal of Foundations of Computer Science, volume 3, pages 81-92 (issn: 0129-0541, eissn: 1793-6373,

Authors: Marché, Claude;

doi: 10.1142/s0129054192000085

THE WORD PROBLEM OF ACD-GROUND THEORIES IS UNDECIDABLE

- Summary
- Subjects
- Metrics

Abstract

We prove that there exists an ACD-ground theory, i.e., an equational theory defined by a set of ground equations plus the associativity and commutativity of two binary symbols * and +, and the distributivity of * over +, for which the word problem is undecidable.

Related Organizations

University of Paris-Sud
France
University of Paris-Saclay
France

Keywords

Decidability of theories and sets of sentences, Word problems (aspects of algebraic structures), Grammars and rewriting systems, Word problems, etc. in computability and recursion theory, equational theory, ground equations

Impact byBIP!

	selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	6
	popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.	Average
	influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	Top 10%
	impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.	Average