A1 Refereed original research article in a scientific journal
Decision questions concerning semilinearity, morphisms, and commutation of languages
Authors: Harju T, Ibarra O, Karhumaki J, Salomaa A
Publication year: 2001
Journal:: Lecture Notes in Computer Science
Journal name in source: AUTOMATA LANGUAGES AND PROGRAMMING, PROCEEDING
Journal acronym: LECT NOTES COMPUT SC
Volume: 2076
First page : 579
Last page: 590
Number of pages: 12
ISBN: 3-540-42287-0
ISSN: 0302-9743
Abstract
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.
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.
UTU Research Portal