Inscriere cercetatori

Daca aveti cont Ad Astra si de Facebook, intrati pe pagina de profil pentru a da dreptul sa va logati pe site doar cu acest buton.

Site nou !

Daca nu va puteti recupera parola (sau aveti alte probleme), scrieti-ne la pagina de contact. Situl vechi se gaseste la adresa


The language (and series) of Hammersley-type processes

Autori: Cosmin Bonchis, Gabriel Istrate, Vlad Rochian

Editorial: Springer Verlag, Proceedings of the 8th Conference on Machines, Computations and Universality (MCU'18), June 28-30, 2018, Fontainebleau, France, Lecture Notes in Computer Science vol 10881 Springer Verlag, p.69-87, 2018.


Want create site? Find Free WordPress Themes and plugins.

We study languages and formal power series associated to (variants of) Hammersley’s process. We show that the ordinary Hammersley process yields a regular language and the Hammersley tree process yields deterministic context-free (but non-regular) languages. For the extension to intervals of the Hammersley process we show that there are two relevant formal language variants. One of them leads to the same class of languages as the ordinary Hammersley tree process. The other one yields non-context-free languages.

The results are motivated by the problem of studying the analog of the famous Ulam-Hammersley problem for heapable sequences. Towards this goal we also give an algorithm for computing formal power series associated to the variants of the Hammersley’s process, that have the formal languages studies in this paper as their support. We employ these algorithms to settle the nature of the scaling constant, conjectured in previous work to be the golden ratio. Our results provide experimental support to this conjecture.

A preprint version of the paper is freely available at

Did you find apk for android? You can find new Free Android Games and apps.