{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,28]],"date-time":"2026-02-28T14:03:05Z","timestamp":1772287385351,"version":"3.50.1"},"reference-count":12,"publisher":"World Scientific Pub Co Pte Lt","issue":"03","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2017,4]]},"abstract":"<jats:p> Let us color the vertices of the grid \u2124<jats:sup>d<\/jats:sup> or the infinite regular tree \ud835\udd4b<jats:sub>d<\/jats:sub>, using a finite number of colors, with the constraint that some predefined pairs of colors are not allowed for adjacent vertices. The set of admissible colorings is called a nearest-neighbor subshift of finite type (SFT). We study \u201cuniform\u201d probability measures on SFT, with the motivation of having an insight into \u201ctypical\u201d admissible configurations. We recall the known results on uniform measures on SFT on grids and we complete the picture by presenting some contributions to the description of uniform measures on SFT on \ud835\udd4b<jats:sub>d<\/jats:sub>. Then we focus on the problem of uniform random sampling of configurations of SFT. We propose a first method based on probabilistic cellular automata, which is valid under some restrictive conditions. Then we concentrate on the case of SFT on \u2124 for which we propose several alternative sampling methods. <\/jats:p>","DOI":"10.1142\/s0129054117500174","type":"journal-article","created":{"date-parts":[[2017,5,21]],"date-time":"2017-05-21T22:16:41Z","timestamp":1495405001000},"page":"263-287","source":"Crossref","is-referenced-by-count":9,"title":["Uniform Sampling of Subshifts of Finite Type on Grids and Trees"],"prefix":"10.1142","volume":"28","author":[{"given":"Jean","family":"Mairesse","sequence":"first","affiliation":[{"name":"Sorbonne Universit\u00e9s, UPMC Univ Paris 06, CNRS, LIP6, 4 place Jussieu 75252 Paris cedex 05, France"}]},{"given":"Ir\u00e8ne","family":"Marcovici","sequence":"additional","affiliation":[{"name":"Institut \u00c9lie Cartan de Lorraine, Universit\u00e9 de Lorraine, Nancy, France"}]}],"member":"219","published-online":{"date-parts":[[2017,5,21]]},"reference":[{"key":"p_1","doi-asserted-by":"publisher","DOI":"10.1051\/ita\/2014018"},{"key":"p_2","doi-asserted-by":"publisher","DOI":"10.1017\/S0143385709000844"},{"key":"p_3","doi-asserted-by":"publisher","DOI":"10.1007\/BF02808205"},{"key":"p_4","doi-asserted-by":"publisher","DOI":"10.1017\/S0001867800006728"},{"key":"p_10","doi-asserted-by":"publisher","DOI":"10.1017\/S0143385711000824"},{"key":"p_12","doi-asserted-by":"publisher","DOI":"10.1007\/s10955-006-9162-3"},{"key":"p_15","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1964-0161372-1"},{"key":"p_18","doi-asserted-by":"publisher","DOI":"10.1007\/BF01009964"},{"key":"p_19","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1948.tb01338.x"},{"issue":"4","key":"p_20","first-page":"569","volume":"6","author":"Toom A.","year":"2000","journal-title":"Markov Process. Related Fields"},{"key":"p_21","doi-asserted-by":"publisher","DOI":"10.1016\/0304-4149(94)90132-5"},{"key":"p_23","doi-asserted-by":"publisher","DOI":"10.1214\/aop\/1176993439"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054117500174","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T16:58:28Z","timestamp":1565110708000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054117500174"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,4]]},"references-count":12,"journal-issue":{"issue":"03","published-online":{"date-parts":[[2017,5,21]]},"published-print":{"date-parts":[[2017,4]]}},"alternative-id":["10.1142\/S0129054117500174"],"URL":"https:\/\/doi.org\/10.1142\/s0129054117500174","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,4]]}}}