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

DOI10.1007/BF02090778MaRDI QIDQ3210188zbMATH OpenFDO

Authors Paliath Narendran

Publication date 1990

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

zbMATH Keywords

decidabilityThue-system

Mathematics Subject Classification ID

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

Recommendations

• A finite Thue system with decidable word problem and without equivalent finite canonical system
• Publication:4503965
• scientific article; zbMATH DE number 4210423
• 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; zbMATH DE number 4216027
• scientific article; zbMATH DE number 4109028
• scientific article; zbMATH DE number 3948242

Cites work

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

Cited in

(11)

• A note on regular classes in special Thue systems
• A finite Thue system with decidable word problem and without equivalent finite canonical system
• Coalgebras for Bisimulation of Weighted Automata over Semirings
• scientific article; zbMATH DE number 1507241 (Why is no real title available?)
• On the regular equivalence problem for regular Thue systems
• A polynomial algorithm testing partial confluence of basic semi-Thue systems
• Calculi in which derivability is decidable by finite interpretations
• scientific article; zbMATH DE number 1389858 (Why is no real title available?)
• A polynomial algorithm testing partial confluence of basic semi-Thue systems
• Canonical systems which produce periodic sets
• Codes modulo finite monadic string-rewriting 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)