PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
Tytuł artykułu

Interpreted Trajectories

Wybrane pełne teksty z tego czasopisma
Identyfikatory
Warianty tytułu
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.
Wydawca
Rocznik
Strony
81--97
Opis fizyczny
bibliogr. 27 poz.
Twórcy
autor
autor
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
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.