Can I read Some Decision Problems Concerning Semilinearity and Commutation on EtoBox?

Some Decision Problems Concerning Semilinearity and Commutation by Tero Harju; Oscar Ibarra; Juhani Karhumäki; Arto Salomaa is a Computer Science article available to read on EtoBox.

What is Some Decision Problems Concerning Semilinearity and Commutation about?

Let M be a class of automata (in a precise sense to be defined) and M c the class obtained by augmenting each automaton in M with finitely many reversal-bounded counters. We show that if the languages defined by M are effectively semilinear, then so are the languages defined by M c , and, hence, their emptiness problem is decidable. We give examples of how this result can be used to show the decidability of certain problems concerning the equivalence of morphisms on languages. We also prove a surprising undecidability result for commutation of languages: given a fixed two-element code K, it is undecidable whether a given context-free language L commutes with K, i.e., LK 1⁄4 KL.

Who reads Some Decision Problems Concerning Semilinearity and Commutation?

Author

Tero Harju; Oscar Ibarra; Juhani Karhumäki; Arto Salomaa

Publisher

Elsevier Science; Elsevier ; Elsevier Inc.; Elsevier BV (ISSN 0022-0000)

Published

2002

Language

EN

Field

Computer Science (Physical Sciences)