Trajectory-Based Embedding Relations

• Autorzy: Domaratzki M.
• Języki publikacji: EN

Abstrakty

EN

We generalize the embedding order to shuffle on trajectories and examine its properties. We give general characterizations of reflexivity, transitivity, anti-symmetry and other properties of binary relations, and investigate the associated decision problems. We also examine the property of convexity of a language with respect to these generalized embedding relations.

Słowa kluczowe

EN

embedding order; shuffle on trajectories; convexity

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2004
• Tom: Vol. 59, nr 4
• Strony: 349--363
• Opis fizyczny: Bibliogr. 23 poz.

Twórcy

autor

Domaratzki M.

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

Bibliografia

• 111 Choffrut. C., Karhumäki, J.: Combinatorics on Words. 329^138, In [18].
• [2] Domaratzki, M.: Deletion along trajectories, Accepted, Theor. Comput. Sci., 2004.
• [3] Domaratzki. M.: Trajectory-based codes. Accepted, Acta Inf., 2004.
• [4] Ehrenfeucht. A., Haussier. D., Rozenberg, G.: On regularity of context-free languages. Theor. Comp. Sci., 23. 1983,311-332.
• [5] Guo. Y., Shyr, H., Thierrin, G.: E-Convex infix codes, Order, 3, 1986. 55-59.
• [6] Haines, L.: On free monoids partially ordered by embedding, J. Comb. Th., 6. 1969, 94-98.
• [7] Hopcroft, J. E., Ullman. J. D.: Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, 1979.
• [8] Hunt. H., Rosenkrantz. D.: Computational parallels between the regular and context-free languages, SIAM J. Comput., 7(1), 1978,99-1 14.
• [9] Jullien, P.: Sur un théoreme d’extension dans la théorie des mots, CR Acad. Sc. Paris (Serie A), 266. 1968, 851-854.
• [10] Jürgensen. H., Shyr, H., Thierrin. G.: Codes and compatible partial orders on free monoids. Algebra and Order: Proceedings of the First International Symposium on Ordered Algebraic Structures, Luminy-Marseilles 1984 (S. Wolfenstein, Ed.), Heldermann Verlag, 1986.
• [11] Kadrie, A., Dare, V., Thomas, D., Subramanian, K.: Algebraic properties of the shuffle over ω-trajectories, Inf Proc. Letters. 80(3), 2001, 139-144.
• [12] Kari, L., Sosik, P.: Language deletions on trajectories, Technical Report 606. Computer Science Department, University of Western Ontario, 2003.
• [13] Kari, L.. Thierrin, G.: k-catenation and applications: k-prefix codes, J. Inf Opt. Sci., 16(2). 1995, 263-276.
• [14] Long, D.: On two infinite hierarchies of prefix codes. Proceedings of the Conference on Ordered Structures and Algebra of Computer Languages (K. Shum. P. Yuen. Eds.), World Scientific. 1993.
• [15] Mateescu. A.: Splicing on routes: a framework of DNA computation. Unconventional Models of Compulation (C. Calude, J. Casti. M. Dinneen. Eds.), Springer, 1998.
• [16] Mateescu, A., Rozenberg, G., Salomaa. A.: Shuffle on trajectories: Syntactic constraints, Theor. Comp. Sci., 197. 1998, 1-56.
• [17] Okhotin. A.: Personal communication, September 2003.
• [18] Rozenberg, G., Salomaa, A. Eds.: Handbook of Formal Languages, Vol. I. Springer-Verlag, 1997.
• [19] Shyr, H.: Free Monoids and Languages. Hon Min Book Company. Taichung. Taiwan. 2001.
• [20] Shyr, H., Thierrin, G.: Hypercodes, Inf. and Cont., 24(1). 1974. 45-54.
• [21] Shyr, H., Thierrin. G.: Codes and binary relations, Séminaire d'Algébre Paul Dubreil. Paris 1975-1976 (A. Dold. B. Eckmann, Eds.), Lecture Notes in Mathematics 586. Springer-Verlag, 1977.
• [22] Thierrin. G., Yu. S. S.: Shuffle relations and codes, J. Inf. Opt. Sei., 12(3), 1991,441-449.
• [23] Yu. S.: Regular Languages, 41-1 10, in [18].