Computing by commuting.

DOI10.1016/j.tcs.2006.01.051zbMath1160.68415OpenAlexW1977870924MaRDI QIDQ2490820

Alexander Okhotin, Michal Kunc, 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

rewriting systemsregular languagesrational relationscommutation of languages

Mathematics Subject Classification ID

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

Related Items (1)

The Reachability Problem over Infinite Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the regular structure of prefix rewriting
• Deleting string rewriting systems preserve regularity
• An application of the matrix representation of transductions
• A note on decidability questions on presentations of word semigroups
• Regular solutions of language inequalities and well quasi-orders
• Unification in a Description Logic with Transitive Closure of Roles
• On the equivalence of linear conjunctive grammars and trellis automata
• Regular canonical systems
• Developments in Language Theory
• Canonical systems which produce periodic sets
• Decidability of Second-Order Theories and Automata on Infinite Trees
• STACS 2005
• Machines, Computations, and Universality
• Formal Reductions of the General Combinatorial Decision Problem

This page was built for publication: Computing by commuting.