Powiadomienia systemowe
- Sesja wygasła!
- Sesja wygasła!
Tytuł artykułu
Autorzy
Wybrane pełne teksty z tego czasopisma
Identyfikatory
Warianty tytułu
Języki publikacji
Abstrakty
We introduce generalized trajectories where the individual symbols are interpreted as operations performed on the operand words. The various previously considered trajectory-based operations can all be expressed in this formalism. It is shown that the generalized operations can simulate Turing machine computations. We consider the equivalence problem and a notion of unambiguity that is sufficient to make equivalence decidable for regular sets of trajectories under nonincreasing interpretations.
Słowa kluczowe
Wydawca
Czasopismo
Rocznik
Tom
Strony
81--97
Opis fizyczny
bibliogr. 27 poz.
Twórcy
autor
autor
autor
- School of Computing, Queenćs University, Kingston, Ontario, Canada K7L3N6, mike.domaratzki@acadiau.ca
Bibliografia
- [1] J. Berstel: Transductions and Context-Free Languages. Teubner, Stuttgart, 1979.
- [2] M. Domaratzki: Deletion along trajectories. Theoretical Computer Science, 320 (2004), 293-313.
- [3] M. Domaratzki: Semantic shuffle on and deletion along trajectories. In Proc. 8th International Conference on Developments on Language Theory, DLT'04, LNCS 3340, Springer-Verlag, Berlin, 2004, 163-174.
- [4] M. Domaratzki: Trajectory-based codes. Acta Informatica, 40 (2004), 491-527.
- [5] M. Domaratzki: Trajectory-based embedding relations. Fundamenta Informatica, 59 (2004), 349-363.
- [6] M. Domaratzki: More words on trajectories. Bulletin of the EATCS, 86 (June 2005), 107-145.
- [7] M. Domaratzki, A. Mateescu, K. Salomaa, S. Yu: Deletion along trajectories and commutative closure. In Proc. of 4th International Conference on Combinatorics on Words (T. Harju, J. Karhumäki, eds.), 2003, 309-319.
- [8] M. Domaratzki, K. Salomaa: Decidability of trajectory-based equations. In Mathematical Foundations of Computer Science,MFCS'04 (J. Fiala, V. Koubek, J. Kratochv´ıl, eds.), LNCS 3153, Springer-Verlag, Berlin, 2004, 723-734. Full version to appear in Theoretical Computer Science.
- [9] M. Domaratzki, K. Salomaa: Codes defined by multiple sets of trajectories. In Proc. 11th International Conference on Automata and Formal Languages, AFL'05 (Z. Ësik, Z. Fülöp, eds.), 2005, 97-111.
- [10] M. Domaratzki, K. Salomaa: Restricted sets of trajectories and decidability of shuffle decompositions. International Journal of Foundations of Computer Science, 16 (2005), 897-912.
- [11] T. Harju, J. Karhumäki: The equivalence problem of multitape finite automata. Theoretical Computer Science, 78 (1991), 347-355.
- [12] T. Harju, J. Karhumäki: Morphisms. In [26], 439-510.
- [13] T. Harju, J. Karhumäki, D. Krob: Remarks on generalized Post correspondence problem. In 13th Annual Symposium on Theoretical Aspects of Computer Science, STACS'96, LNCS 1046, Springer-Verlag, Berlin, 1996, 39-48.
- [14] T. Harju, A. Mateescu, A. Salomaa: Shuffle on trajectories: The Schützenberger product and related operations. In Mathematical Foundations of Computer Science, MFCS'98 (L. Brim, J. Gruska, J. Zlatuska, eds.), LNCS 1450, Springer-Verlag, Berlin, 1998, 503-511.
- [15] J.E. Hopcroft, J.D. Ullman: Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, 1979.
- [16] L. Kari, S. Konstantinidis, P. Sos´ık: Substitutions on trajectories. In Theory is Forever (J. Karhumäki, H. Maurer, G. P˘aun, G. Rozenberg, eds.), LNCS 3113, Springer-Verlag, Berlin, 2004, 145-158.
- [17] L. Kari, S. Konstantinidis, P. Sos´ık: Substitutions, trajectories and noisy channels. In Implementation and Application of Automata, CIAA'04 (M. Domaratzki, A. Okhotin, K. Salomaa, S. Yu, eds.), LNCS 3317, Springer-Verlag, Berlin, 2005, 202-212.
- [18] L. Kari, S. Konstantinidis, P. Sos´ık: Operations on trajectorieswith applications to coding and bioinformatics. International Journal of Foundations of Computer Science, 16 (2005), 531-546.
- [19] L. Kari, P. Sos´ık: Aspects of shuffle and deletion on trajectories. Theoretical Computer Science, 332 (2005), 47-61.
- [20] E. Kinber: The inclusion problem for some classes of deterministic multitape automata. Theoretical Computer Science, 26 (1983), 1-24.
- [21] A. Mateescu: CD grammar systems and trajectories. Acta Cybernetica, 12 (1997), 141-157.
- [22] A. Mateescu: Splicing on routes: a framework of DNA computation. In Unconventional Models of Computation (C. Calude, J. Casti, M. Dinneen, eds.), Springer-Verlag, Singapore, 1998, 273-285.
- [23] A. Mateescu: Words on trajectories. Bulletin of the EATCS, 65 (1998), 118-135.
- [24] A.Mateescu, G. Rozenberg,A. Salomaa: Shuffle on trajectories: Syntactic constraints. Theoretical Computer Science, 197 (1998), 1-56.
- [25] A. Mateescu, K. Salomaa, S. Yu: On fairness of many dimensional trajectories. J. Automata, Languages and Combinatorics, 5 (2000), 145-157.
- [26] G. Rozenberg, A. Salomaa, eds.: Handbook of Formal Languages, Vol. I-III. Springer-Verlag, Berlin, 1997.
- [27] S. Yu: Regular languages. In [26], 41-110.
Typ dokumentu
Bibliografia
Identyfikator YADDA
bwmeta1.element.baztech-article-BUS2-0010-0091