A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
Decision questions concerning semilinearity, morphisms, and commutation of languages
Tekijät: Harju T, Ibarra O, Karhumaki J, Salomaa A
Julkaisuvuosi: 2001
Lehti:: Lecture Notes in Computer Science
Tietokannassa oleva lehden nimi: AUTOMATA LANGUAGES AND PROGRAMMING, PROCEEDING
Lehden akronyymi: LECT NOTES COMPUT SC
Vuosikerta: 2076
Aloitussivu: 579
Lopetussivu: 590
Sivujen määrä: 12
ISBN: 3-540-42287-0
ISSN: 0302-9743
Tiivistelmä
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.
Turun yliopiston Tutkimustietojärjestelmän portaali