Geodesic
EMSO-definability of some languages with event structures
Zapiski Nauchnykh Seminarov POMI, Computational complexity theory. Part VIII, Tome 304 (2003), pp. 128-140 
K. V. Shahbazyan; Yu. G. Shoukourian. EMSO-definability of some languages with event structures. Zapiski Nauchnykh Seminarov POMI, Computational complexity theory. Part VIII, Tome 304 (2003), pp. 128-140. http://geodesic.mathdoc.fr/item/ZNSL_2003_304_a7/
@article{ZNSL_2003_304_a7,
     author = {K. V. Shahbazyan and Yu. G. Shoukourian},
     title = {EMSO-definability of some languages with event structures},
     journal = {Zapiski Nauchnykh Seminarov POMI},
     pages = {128--140},
     year = {2003},
     volume = {304},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ZNSL_2003_304_a7/}
}
TY  - JOUR
AU  - K. V. Shahbazyan
AU  - Yu. G. Shoukourian
TI  - EMSO-definability of some languages with event structures
JO  - Zapiski Nauchnykh Seminarov POMI
PY  - 2003
SP  - 128
EP  - 140
VL  - 304
UR  - http://geodesic.mathdoc.fr/item/ZNSL_2003_304_a7/
LA  - ru
ID  - ZNSL_2003_304_a7
ER  - 
%0 Journal Article
%A K. V. Shahbazyan
%A Yu. G. Shoukourian
%T EMSO-definability of some languages with event structures
%J Zapiski Nauchnykh Seminarov POMI
%D 2003
%P 128-140
%V 304
%U http://geodesic.mathdoc.fr/item/ZNSL_2003_304_a7/
%G ru
%F ZNSL_2003_304_a7

Voir la notice du chapitre de livre provenant de la source Math-Net.Ru

Languages of words, trees, and pictures with related event structures are considered. An event structure is defined for a word (tree, picture) based on the event structures of individual letters and homogeneous relations between the events of letters on neighboring positions. The main problem considered is the problem of EMSO-definability of two language classes: the class of languages with cyclic event structures and the class of languages with acyclic event structures.

[1] G. Winskel, M. Nielsen, Models for concurrency, Handbook of Logic in Computer Science, 4, Oxford Univ. Press, 1995 | MR

[2] K. V. Shakhbazyan, Yu. H. Shoukourian, “Logically definable languages of computations in one class of flow event structures”, Dokl. Nats. Akad. Nauk Armen., 102:1 (2002), 16–22 | MR

[3] W. Thomas, “Languages, automata, and logic”, Handbook of Formal Languages, 102, eds. G. Rozenberg, A.Salomaa, Springer, 1997, 389–455 | MR

[4] D. Giammarresi, A. Restivo,, “Two-dimensional languages”, Formal Language Theory, Vol. III, Springer-Verlag, New York, 1996 | MR | Zbl

[5] W. Thomas, Languages, automata, and logic, Bericht 9607, Institute fuer informatik und praktische mathematik der Christian-Albrechts-Universitaet zu Kiel, D-24098, Kiel