A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
Some decision problems concerning semilinearity and commutation
Tekijät: Harju T, Ibarra O, Karhumaki J, Salomaa A
Kustantaja: ACADEMIC PRESS INC ELSEVIER SCIENCE
Julkaisuvuosi: 2002
Lehti:: Journal of Computer and System Sciences
Tietokannassa oleva lehden nimi: JOURNAL OF COMPUTER AND SYSTEM SCIENCES
Lehden akronyymi: J COMPUT SYST SCI
Vuosikerta: 65
Numero: 2
Aloitussivu: 278
Lopetussivu: 294
Sivujen määrä: 17
ISSN: 0022-0000
DOI: https://doi.org/10.1006/jcss.2002.1836
Tiivistelmä
Let W be a class of automata (in a precise sense to be defined) and 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 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 = KL. (C) 2002 Elsevier Science (USA).
Let W be a class of automata (in a precise sense to be defined) and 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 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 = KL. (C) 2002 Elsevier Science (USA).
Turun yliopiston Tutkimustietojärjestelmän portaali