Decision questions concerning semilinearity, morphisms, and commutation of languages



: Harju T, Ibarra O, Karhumaki J, Salomaa A

: 2001

Lecture Notes in Computer Science

AUTOMATA LANGUAGES AND PROGRAMMING, PROCEEDING

: LECT NOTES COMPUT SC

: 2076

: 579

: 590

: 12

: 3-540-42287-0

: 0302-9743


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



Last updated on 2025-13-10 at 14:23