When is an extension of a specification consistent? Decidable and undecidable cases

DOI10.1016/S0747-7171(08)80150-2zbMath0746.68062MaRDI QIDQ1186708

Friedrich Otto

Publication date: 28 June 1992

Published in: Journal of Symbolic Computation (Search for Journal in Brave)

zbMATH Keywords

specificationstring rewriting systemabstract data typesconsistent enrichment

Mathematics Subject Classification ID

Abstract data types; algebraic specification (68Q65) Grammars and rewriting systems (68Q42)

Related Items

Codes modulo finite monadic string-rewriting systems, On weakly confluent monadic string-rewriting systems, Uniform decision problems for automatic semigroups., Some undecidability results concerning the property of preserving regularity

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Decidable sentences of Church-Rosser congruences
• Some undecidability results for non-monadic Church-Rosser Thue systems
• On two problems related to cancellativity
• On deciding whether a monoid is a free monoid or is a group
• Systems of reductions
• Thue congruences and the Church-Rosser property
• The algebraic specification of abstract data types
• Presentations of groups and monoids
• Cancellativity in finitely presented semigroups
• Undecidable questions related to Church-Rosser Thue systems
• Computing with rewrite systems
• Confluent and Other Types of Thue Systems
• Rewriting techniques for program synthesis