A polynomial algorithm testing partial confluence of basic semi-Thue systems

DOI10.1016/S0304-3975(97)00145-XzbMATH Open0908.68108WikidataQ128037015 ScholiaQ128037015MaRDI QIDQ1127336FDOQ1127336

Authors: Géraud Sénizergues 

Publication date: 13 August 1998

Published in: Theoretical Computer Science (Search for Journal in Brave)

Recommendations

• A polynomial algorithm testing partial confluence of basic semi-Thue systems
• Rewriting systems and word problems in a free partially commutative monoid
• scientific article; zbMATH DE number 1418332
• scientific article; zbMATH DE number 1615237
• Some polynomial-time algorithms for finite monadic Church-Rosser Thue systems

zbMATH Keywords

confluencesemi-Thue systemstwo-tape finite automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Parallel algorithms in computer science (68W10)

Cites Work

• Efficient string matching
• Title not available (Why is that?)
• Title not available (Why is that?)
• Confluent Reductions: Abstract Properties and Applications to Term Rewriting Systems
• Finite-Turn Pushdown Automata
• The equivalence problem for deterministic finite-turn pushdown automata
• The equivalence problem of multitape finite automata
• An algebraic theory of graph reduction
• NTS languages are deterministic and congruential
• On deciding the confluence of a finite string-rewriting system on a given congruence class
• Title not available (Why is that?)
• Monadic Thue systems
• Infinite regular Thue systems
• Title not available (Why is that?)
• An improvement on Valiant's decision procedure for equivalence of deterministic finite turn pushdown machines
• The problem of deciding confluence on a given congruence class is tractable for finite special string-rewriting systems
• On weakly confluent monadic string-rewriting systems
• The equivalence of pre-NTS grammars is decidable
• Title not available (Why is that?)
• A Polynomial Time Algorithm for Deciding the Equivalence Problem for 2-Tape Deterministic Finite State Acceptors
• The equivalence and inclusion problems for NTS languages
• Title not available (Why is that?)
• Title not available (Why is that?)
• Some decision problems about controlled rewriting systems
• A characterisation of deterministic context-free languages by means of right-congruences
• The equivalence problem for deterministic pushdown automata is decidable
• It is decidable whether a monadic thue system is canonical over a regular set
• Title not available (Why is that?)
• A polynomial algorithm testing partial confluence of basic semi-Thue systems

Cited In (6)

• Lambda-confluence for context rewriting systems
• \(L(A)=L(B)\)? decidability results from complete formal systems
• A polynomial algorithm testing partial confluence of basic semi-Thue systems
• A Polynomial-Time Algorithm to Check Closedness of Simple Second Order Mixed-Integer Sets
• Rational subsets of partially reversible monoids
• LARS: a learning algorithm for rewriting systems

This page was built for publication: A polynomial algorithm testing partial confluence of basic semi-Thue systems

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