Contextual Grammars with Uniform Sets of Trajectories

• Autorzy: Okhotin A. , Salomaa K.
• Języki publikacji: EN

Abstrakty

EN

A uniform contextual grammar with contexts shuffled along trajectories uses the same set of trajectories for each context. We prove that when the alphabet has at least two symbols, the non-uniform contextual grammars with trajectories are strictly more powerful than the uniform variant. For unary alphabets the generative power of the two variants coincides, and the same is true for grammars where the sets of trajectories are regular or context-free.

Słowa kluczowe

EN

contextual grammars; trajectory; regular language; context-free language

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2005
• Tom: Vol. 64, nr 1-4
• Strony: 341--351
• Opis fizyczny: Bibliogr. 16 poz.

Twórcy

autor

Okhotin A.

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

autor

Salomaa K.

• School of Computing, Queen’s University Kingston, Ontario K7L 3N6, Canada

Bibliografia

• [1] Domaratzki, M.: Semantic shuffle on and deletion along trajectories, Developments in Language Theory, DLT’04, Auckland, New Zealand, December 2004, Lect. Notes Comput. Sci. 3340, Springer-Verlag, 2004, 163–174.
• [2] Ehrenfeucht, A., Păun, Gh., Rozenberg, G.: Contextual grammars and formal languages, in: Handbook of Formal Languages, Vol. 2, (G. Rozenberg, A. Salomaa, Eds.), Springer-Verlag, 1997, 237–293.
• [3] Ilie, L.: On the computational complexity of contextual languages, Theoretical Computer Science 183, 1997, 33–44.
• [4] Kudlek, M., Marcus, S., Mateescu, A.: Contextual grammars with distributed catenation and shuffle, Fundamentals of Computation Theory, FCT’97, Lect. Notes Comput. Sci. 1279, Springer-Verlag, 1997, 269–280.
• [5] Marcus, S.: Contextual grammars, Rev. Roum. Math. Pures et Appl. 14, 1969, 1525–1534,
• [6] Marcus, S.: Deux types nouveaux de grammaires g´en´eratives, Cah. Ling. Th. Appl. 6, 1969, 69–74.
• [7] Marcus, S.: Contextual grammars and natural languages, in: Handbook of Formal Languages, Vol. 2, (G. Rozenberg, A. Salomaa, Eds.), Springer-Verlag, 1997, 215–235.
• [8] Martin-Vide, C., Mateescu, A., Salomaa, A., Rozenberg, G.: Contexts on trajectories, International Journal of Computer Mathematics 73, 1999, 15–36. (Preliminary version appeared as TUCS Technical Report No 214, 1998.)
• [9] Martin-Vide, C., Mateescu, A.: Contextual grammars with trajectories, Proceedings of DLT’99, (G. Rozenberg, W. Thomas Eds.), World Scientific, Singapore, 2000, 362–374.
• [10] Mateescu, A.: Marcus contextual grammars with shuffled contexts, in: Mathematical Aspects of Natural and Formal Languages, (Gh. Păun, Ed.),World Scientific, Singapore, 1994, 275–284.
• [11] Mateescu, A., Salomaa, A., Rozenberg, G.: Shuffle on trajectories: Syntactic constraints, Theoretical Computer Science 197, 1998, 1–56.
• [12] Păun, Gh.: Marcus contextual grammars. After 25 years, Bulletin of the EATCS 52, 1994, 263–273.
• [13] Păun, Gh.: Marcus contextual grammars, Kluwer Academic Publishers, 1997.
• [14] Păun, Gh. (Ed.): Mathematical Aspects of Natural and Formal Languages, World Scientific Series in Computer Science, Vol. 43, Singapore, 1994.
• [15] Păun, Gh., Rozenberg, G., Salomaa, A.: Grammars based on the shuffle operation, J. Universal Computer Science 1, 1995, 67–81.
• [16] Păun, Gh., Salomaa, A.: Thin and slender languages, Discrete Applied Mathematics 61, 1995, 257–270