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

DOI10.1007/BF02090778zbMath0722.68071MaRDI QIDQ3210188

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)

Related Items (3)

Coalgebras for Bisimulation of Weighted Automata over Semirings ⋮ A polynomial algorithm testing partial confluence of basic semi-Thue systems ⋮ A polynomial algorithm testing partial confluence of basic semi-Thue systems

Cites Work

• Unnamed Item
• On ground-confluence of term rewriting systems
• The equivalence and inclusion problems for NTS languages
• Thue systems as rewriting systems
• On deciding the confluence of a finite string-rewriting system on a given congruence class
• Testing for the Church-Rosser property
• 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
• The equivalence problem for deterministic finite-turn pushdown automata

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