It is decidable whether a monadic thue system is canonical over a regular set

DOI10.1007/BF02090778zbMATH Open0722.68071MaRDI QIDQ3210188FDOQ3210188

Authors: Paliath Narendran 

Publication date: 1990

Published in: Mathematical Systems Theory (Search for Journal in Brave)

Recommendations

• A finite Thue system with decidable word problem and without equivalent finite canonical system
• Publication:4503965
• scientific article
• scientific article; zbMATH DE number 3880651
• Some undecidability results for non-monadic Church-Rosser Thue systems
• On countable chains having decidable monadic theory
• THE COMPLEXITY OF DECIDING CODE AND MONOID PROPERTIES FOR REGULAR SETS
• scientific article
• scientific article
• scientific article; zbMATH DE number 3948242

zbMATH Keywords

decidabilityThue-system

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Grammars and rewriting systems (68Q42)

Cites Work

• Title not available (Why is that?)
• The equivalence problem for deterministic finite-turn pushdown automata
• On ground-confluence of term rewriting systems
• On deciding the confluence of a finite string-rewriting system on a given congruence class
• Testing for the Church-Rosser property
• Thue systems as rewriting systems
• An improvement on Valiant's decision procedure for equivalence of deterministic finite turn pushdown machines
• The equivalence and inclusion problems for NTS languages
• On Proving Uniform Termination and Restricted Termination of Rewriting Systems

Cited In (11)

• A note on regular classes in special Thue systems
• Coalgebras for Bisimulation of Weighted Automata over Semirings
• Canonical systems which produce periodic sets
• Calculi in which derivability is decidable by finite interpretations
• Title not available (Why is that?)
• A polynomial algorithm testing partial confluence of basic semi-Thue systems
• A polynomial algorithm testing partial confluence of basic semi-Thue systems
• A finite Thue system with decidable word problem and without equivalent finite canonical system
• Title not available (Why is that?)
• Codes modulo finite monadic string-rewriting systems
• On the regular equivalence problem for regular Thue systems

This page was built for publication: It is decidable whether a monadic thue system is canonical over a regular set

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3210188)