Interpreted Trajectories

• Autorzy: Domaratzki M. , Rozenberg G. , Salomaa K.
• Języki publikacji: EN

Abstrakty

EN

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

EN

formal languages; decidability; trajectories; regularity; unambiguity

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2006
• Tom: Vol. 73, nr 1-2
• Strony: 81--97
• Opis fizyczny: bibliogr. 27 poz.

Twórcy

autor

Domaratzki M.

autor

Rozenberg G.

autor

Salomaa K.

• School of Computing, Queenćs University, Kingston, Ontario, Canada K7L3N6,

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.