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

DOI10.1007/3-540-59200-8_57MaRDI QIDQ5055831zbMATH OpenOpenAlexFDO

Authors Géraud Sénizergues

Publication date 9 December 2022

Published in Rewriting Techniques and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-59200-8_57

zbMATH Keywords

confluencesemi-Thue systemstwo-tape finite automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Grammars and rewriting systems (68Q42) Thue and Post systems, etc. (03D03)

Recommendations

• A polynomial algorithm testing partial confluence of basic semi-Thue systems
• scientific article; zbMATH DE number 176737
• Rewriting systems and word problems in a free partially commutative monoid
• scientific article; zbMATH DE number 1418332
• scientific article; zbMATH DE number 1615237

Cites work

• scientific article; zbMATH DE number 3684913 (Why is no real title available?)
• scientific article; zbMATH DE number 3788014 (Why is no real title available?)
• scientific article; zbMATH DE number 43246 (Why is no real title available?)
• scientific article; zbMATH DE number 176741 (Why is no real title available?)
• scientific article; zbMATH DE number 3612461 (Why is no real title available?)
• scientific article; zbMATH DE number 1142312 (Why is no real title available?)
• scientific article; zbMATH DE number 1142316 (Why is no real title available?)
• scientific article; zbMATH DE number 789389 (Why is no real title available?)
• scientific article; zbMATH DE number 3430632 (Why is no real title available?)
• A Polynomial Time Algorithm for Deciding the Equivalence Problem for 2-Tape Deterministic Finite State Acceptors
• A characterisation of deterministic context-free languages by means of right-congruences
• An algebraic theory of graph reduction
• Church-Rosser controlled rewriting systems and equivalence problems for deterministic context-free languages
• Confluent Reductions: Abstract Properties and Applications to Term Rewriting Systems
• Finite-Turn Pushdown Automata
• Infinite regular Thue systems
• It is decidable whether a monadic thue system is canonical over a regular set
• Monadic Thue systems
• NTS languages are deterministic and congruential
• On deciding the confluence of a finite string-rewriting system on a given congruence class
• On weakly confluent monadic string-rewriting systems
• Some decision problems about controlled rewriting systems
• The equivalence and inclusion problems for NTS languages
• The equivalence of pre-NTS grammars is decidable
• The equivalence problem of multitape finite automata
• The problem of deciding confluence on a given congruence class is tractable for finite special string-rewriting systems

Cited in

(2)

• 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

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 Q5055831)