Computing by commuting.

DOI10.1016/J.TCS.2006.01.051MaRDI QIDQ2490820zbMATH OpenOpenAlexFDO

Authors Michal Kunc, Alexander Okhotin, Juhani Karhumäki

Publication date 18 May 2006

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

Full work available at URL https://doi.org/10.1016/j.tcs.2006.01.051

zbMATH Keywords

commutation of languagesrational relationsregular languagesrewriting systems

Mathematics Subject Classification ID

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

Recommendations

• Deleting string rewriting systems preserve regularity
• Regularity and context-freeness over word rewriting systems
• scientific article; zbMATH DE number 2040918
• Publication:4734777
• Deleting powers in words

Cites work

• A note on decidability questions on presentations of word semigroups
• An application of the matrix representation of transductions
• Canonical systems which produce periodic sets
• Decidability of Second-Order Theories and Automata on Infinite Trees
• Deleting string rewriting systems preserve regularity
• Developments in Language Theory
• Formal Reductions of the General Combinatorial Decision Problem
• scientific article; zbMATH DE number 5643878 (Why is no real title available?)
• scientific article; zbMATH DE number 3660804 (Why is no real title available?)
• scientific article; zbMATH DE number 3639163 (Why is no real title available?)
• scientific article; zbMATH DE number 2038714 (Why is no real title available?)
• scientific article; zbMATH DE number 2155196 (Why is no real title available?)
• scientific article; zbMATH DE number 789389 (Why is no real title available?)
• scientific article; zbMATH DE number 3305019 (Why is no real title available?)
• scientific article; zbMATH DE number 3310089 (Why is no real title available?)
• scientific article; zbMATH DE number 3339488 (Why is no real title available?)
• scientific article; zbMATH DE number 3366846 (Why is no real title available?)
• scientific article; zbMATH DE number 3413820 (Why is no real title available?)
• Machines, Computations, and Universality
• On the equivalence of linear conjunctive grammars and trellis automata
• On the regular structure of prefix rewriting
• Regular canonical systems
• Regular solutions of language inequalities and well quasi-orders
• STACS 2005
• Unification in a description logic with transitive closure of roles

Cited in

(3)

• The Reachability Problem over Infinite Graphs
• scientific article; zbMATH DE number 4033113 (Why is no real title available?)
• Deleting powers in words

This page was built for publication: Computing by commuting.

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