{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,4,26]],"date-time":"2024-04-26T21:50:10Z","timestamp":1714168210495},"reference-count":77,"publisher":"Elsevier BV","issue":"6","license":[{"start":{"date-parts":[[2016,9,1]],"date-time":"2016-09-01T00:00:00Z","timestamp":1472688000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2020,9,1]],"date-time":"2020-09-01T00:00:00Z","timestamp":1598918400000},"content-version":"vor","delay-in-days":1461,"URL":"http:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":["elsevier.com","sciencedirect.com"],"crossmark-restriction":true},"short-container-title":["Journal of Computer and System Sciences"],"published-print":{"date-parts":[[2016,9]]},"DOI":"10.1016\/j.jcss.2016.01.005","type":"journal-article","created":{"date-parts":[[2016,3,9]],"date-time":"2016-03-09T17:03:10Z","timestamp":1457542990000},"page":"959-1006","update-policy":"http:\/\/dx.doi.org\/10.1016\/elsevier_cm_policy","source":"Crossref","is-referenced-by-count":4,"title":["A logical approach to locality in pictures languages"],"prefix":"10.1016","volume":"82","author":[{"given":"Etienne","family":"Grandjean","sequence":"first","affiliation":[]},{"ORCID":"http:\/\/orcid.org\/0000-0002-3552-5566","authenticated-orcid":false,"given":"Fr\u00e9d\u00e9ric","family":"Olive","sequence":"additional","affiliation":[]}],"member":"78","reference":[{"key":"10.1016\/j.jcss.2016.01.005_br0010","series-title":"CSL","first-page":"397","article-title":"Local problems, planar local problems and linear time","volume":"vol. 2471","author":"Barbanchon","year":"2002"},{"issue":"3\/4","key":"10.1016\/j.jcss.2016.01.005_br0020","first-page":"161","article-title":"Formal language characterizations of P, NP, and PSPACE","volume":"13","author":"Borchert","year":"2008","journal-title":"J. Autom. Lang. Comb."},{"key":"10.1016\/j.jcss.2016.01.005_br0030","series-title":"The Classical Decision Problem","author":"B\u00f6rger","year":"2001"},{"key":"10.1016\/j.jcss.2016.01.005_br0040","doi-asserted-by":"crossref","first-page":"66","DOI":"10.1002\/malq.19600060105","article-title":"Weak second-order arithmetic and finite automata","volume":"6","author":"B\u00fcchi","year":"1960","journal-title":"Z. Math. Log. Grundl. Math."},{"key":"10.1016\/j.jcss.2016.01.005_br0050","series-title":"STOC","first-page":"187","article-title":"A hierarchy for nondeterministic time complexity","author":"Cook","year":"1972"},{"key":"10.1016\/j.jcss.2016.01.005_br0060","series-title":"Graph Structure and Monadic Second-Order Logic, a Language Theoretic Approach","author":"Courcelle","year":"2012"},{"key":"10.1016\/j.jcss.2016.01.005_br0070","series-title":"Cellular Automata: a Parallel Model","year":"1998"},{"issue":"4","key":"10.1016\/j.jcss.2016.01.005_br0080","doi-asserted-by":"crossref","DOI":"10.1145\/1276920.1276923","article-title":"First-order queries on structures of bounded degree are computable with constant delay","volume":"8","author":"Durand","year":"2007","journal-title":"ACM Trans. Comput. Log."},{"key":"10.1016\/j.jcss.2016.01.005_br0090","series-title":"Finite Model Theory","author":"Ebbinghaus","year":"1995"},{"key":"10.1016\/j.jcss.2016.01.005_br0100","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1090\/S0002-9947-1961-0139530-9","article-title":"Decision problem of finite automata design and related arithmetics","volume":"98","author":"Elgot","year":"1961","journal-title":"Trans. Am. Math. Soc."},{"key":"10.1016\/j.jcss.2016.01.005_br0110","series-title":"Complexity of Computation, SIAM-AMS Proceedings","first-page":"43","article-title":"Generalized first-order spectra and polynomial-time recognizable sets","author":"Fagin","year":"1974"},{"key":"10.1016\/j.jcss.2016.01.005_br0120","doi-asserted-by":"crossref","first-page":"89","DOI":"10.1002\/malq.19750210112","article-title":"Monadic generalized spectra","volume":"21","author":"Fagin","year":"1975","journal-title":"Z. Math. Log. Grundl. Math."},{"key":"10.1016\/j.jcss.2016.01.005_br0130","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1002\/malq.19750210117","article-title":"A spectrum hierarchy","volume":"21","author":"Fagin","year":"1975","journal-title":"Z. Math. Log. Grundl. Math."},{"issue":"1","key":"10.1016\/j.jcss.2016.01.005_br0140","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1016\/0304-3975(93)90218-I","article-title":"Finite-model theory\u2014a personal perspective","volume":"116","author":"Fagin","year":"1993","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"10.1016\/j.jcss.2016.01.005_br0160","doi-asserted-by":"crossref","first-page":"78","DOI":"10.1006\/inco.1995.1100","article-title":"On monadic np vs. monadic co-np","volume":"120","author":"Fagin","year":"1995","journal-title":"Inf. Comput."},{"key":"10.1016\/j.jcss.2016.01.005_br0180","series-title":"Logic and Automata: History and Perspectives [in Honor of Wolfgang Thomas]","volume":"vol. 2","year":"2008"},{"key":"10.1016\/j.jcss.2016.01.005_br0190","series-title":"Logic Colloquium'81","first-page":"105","article-title":"On local and nonlocal properties","author":"Gaifman","year":"1982"},{"key":"10.1016\/j.jcss.2016.01.005_br0200","series-title":"Developments in Language Theory","first-page":"304","article-title":"Computing languages by (bounded) local sets","volume":"vol. 2710","author":"Giammarresi","year":"2003"},{"issue":"2&3","key":"10.1016\/j.jcss.2016.01.005_br0210","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1142\/S021800149200014X","article-title":"Recognizable picture languages","volume":"6","author":"Giammarresi","year":"1992","journal-title":"Int. J. Pattern Recognit. Artif. Intell."},{"issue":"3","key":"10.1016\/j.jcss.2016.01.005_br0220","doi-asserted-by":"crossref","first-page":"399","DOI":"10.3233\/FI-1996-253411","article-title":"Two-dimensional finite state recognizability","volume":"25","author":"Giammarresi","year":"1996","journal-title":"Fundam. Inform."},{"key":"10.1016\/j.jcss.2016.01.005_br0230","series-title":"Handbook of Theoretical Computer Science","first-page":"215","article-title":"Two-dimensional languages","volume":"vol. 3","author":"Giammarresi","year":"1997"},{"issue":"1","key":"10.1016\/j.jcss.2016.01.005_br0240","doi-asserted-by":"crossref","first-page":"32","DOI":"10.1006\/inco.1996.0018","article-title":"Monadic second-order logic over rectangular pictures and recognizability by tiling systems","volume":"125","author":"Giammarresi","year":"1996","journal-title":"Inf. Comput."},{"key":"10.1016\/j.jcss.2016.01.005_br0250","series-title":"Proceedings of 6th IEEE Conference on Structure in Complexity Theory","first-page":"35","article-title":"Capturing complexity classes by fragments of second order logic","volume":"vol. 101","author":"Gr\u00e4del","year":"1992"},{"key":"10.1016\/j.jcss.2016.01.005_br0260","article-title":"Finite Model Theory and Its Applications","author":"Gr\u00e4del","year":"2007"},{"issue":"1\u20132","key":"10.1016\/j.jcss.2016.01.005_br0270","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1016\/S0304-3975(98)00308-9","article-title":"On logics with two variables","volume":"224","author":"Gr\u00e4del","year":"1999","journal-title":"Theor. Comput. Sci."},{"key":"10.1016\/j.jcss.2016.01.005_br0280","doi-asserted-by":"crossref","first-page":"136","DOI":"10.1016\/0022-0000(90)90009-A","article-title":"First-order spectra with one variable","volume":"40","author":"Grandjean","year":"1990","journal-title":"J. Comput. Syst. Sci."},{"key":"10.1016\/j.jcss.2016.01.005_br0290","doi-asserted-by":"crossref","first-page":"546","DOI":"10.1016\/j.jcss.2003.09.002","article-title":"Graph properties checkable in linear time in the number of vertices","volume":"68","author":"Grandjean","year":"2004","journal-title":"J. Comput. Syst. Sci."},{"key":"10.1016\/j.jcss.2016.01.005_br0300","series-title":"Proc. Annual Conference of the EACSL","article-title":"Descriptive complexity of picture languages","author":"Grandjean","year":"2012"},{"issue":"1","key":"10.1016\/j.jcss.2016.01.005_br0310","doi-asserted-by":"crossref","first-page":"196","DOI":"10.1137\/S0097539799360240","article-title":"Machine-independent characterizations and complete problems for deterministic linear time","volume":"32","author":"Grandjean","year":"2002","journal-title":"SIAM J. Comput."},{"issue":"1","key":"10.1016\/j.jcss.2016.01.005_br0320","doi-asserted-by":"crossref","first-page":"112","DOI":"10.1145\/343369.343386","article-title":"Locality of order-invariant first-order formulas","volume":"1","author":"Grohe","year":"2000","journal-title":"ACM Trans. Comput. Log."},{"key":"10.1016\/j.jcss.2016.01.005_br0330","series-title":"The Theory of Models","first-page":"132","article-title":"Model-theoretic methods in the study of elementary logic","author":"Hanf","year":"1965"},{"issue":"4","key":"10.1016\/j.jcss.2016.01.005_br0340","doi-asserted-by":"crossref","first-page":"1751","DOI":"10.2307\/2586810","article-title":"Notions of locality and their logical characterizations over finite models","volume":"64","author":"Hella","year":"1999","journal-title":"J. Symb. Log."},{"key":"10.1016\/j.jcss.2016.01.005_br0350","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0539-5","article-title":"Descriptive Complexity","author":"Immerman","year":"1999"},{"key":"10.1016\/j.jcss.2016.01.005_br0360","series-title":"TAMC","first-page":"511","article-title":"A time hierarchy theorem for nondeterministic cellular automata","volume":"vol. 4484","author":"Iwamoto","year":"2007"},{"key":"10.1016\/j.jcss.2016.01.005_br0370","series-title":"Developments in Language Theory, Proceedings of the 13th International Conference","first-page":"288","article-title":"Subshifts, languages and logic","volume":"vol. 5583","author":"Jeandel","year":"2009"},{"key":"10.1016\/j.jcss.2016.01.005_br0380","series-title":"Proc. Nat. Acad. Sci. U.S.A.","first-page":"365","article-title":"Entscheidungsproblem reduced to the forall-exists-forall case","volume":"vol. 48","author":"Kahr","year":"1962"},{"key":"10.1016\/j.jcss.2016.01.005_br0390","series-title":"Handbook of Natural Computing","first-page":"3","article-title":"Basic concepts of cellular automata","volume":"vol. 1","author":"Kari","year":"2012"},{"issue":"3","key":"10.1016\/j.jcss.2016.01.005_br0400","doi-asserted-by":"crossref","first-page":"786","DOI":"10.1137\/130943625","article-title":"Regular graphs and the spectra of two-variable logic with counting","volume":"44","author":"Kopczynski","year":"2015","journal-title":"SIAM J. Comput."},{"issue":"6","key":"10.1016\/j.jcss.2016.01.005_br0410","doi-asserted-by":"crossref","first-page":"555","DOI":"10.1080\/03081079.2012.695896","article-title":"Nondeterministic cellular automata and languages","volume":"41","author":"Kutrib","year":"2012","journal-title":"Int. J. Gen. Syst."},{"key":"10.1016\/j.jcss.2016.01.005_br0420","series-title":"Recognizable picture languages and domino tiling","author":"Latteux","year":"1994"},{"issue":"2","key":"10.1016\/j.jcss.2016.01.005_br0430","doi-asserted-by":"crossref","first-page":"160","DOI":"10.1006\/inco.1997.2659","article-title":"Context-sensitive string languages and recognizable picture languages","volume":"138","author":"Latteux","year":"1997","journal-title":"Inf. Comput."},{"issue":"1\u20132","key":"10.1016\/j.jcss.2016.01.005_br0440","doi-asserted-by":"crossref","first-page":"275","DOI":"10.1016\/S0304-3975(96)00283-6","article-title":"Recognizable picture languages and domino tiling","volume":"178","author":"Latteux","year":"1997","journal-title":"Theor. Comput. Sci."},{"key":"10.1016\/j.jcss.2016.01.005_br0450","series-title":"Proc. 14th Symposium on Theoretical Aspect of Computer Science","first-page":"143","article-title":"A logical characterisation of linear time on nondeterministic Turing machines","author":"Lautemann","year":"1999"},{"issue":"1","key":"10.1016\/j.jcss.2016.01.005_br0460","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1145\/343369.343376","article-title":"Logics with counting and local properties","volume":"1","author":"Libkin","year":"2000","journal-title":"ACM Trans. Comput. Log."},{"issue":"1","key":"10.1016\/j.jcss.2016.01.005_br0470","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1145\/371282.371388","article-title":"Logics capturing local properties","volume":"2","author":"Libkin","year":"2001","journal-title":"ACM Trans. Comput. Log."},{"key":"10.1016\/j.jcss.2016.01.005_br0480","series-title":"Elements of Finite Model Theory","author":"Libkin","year":"2004"},{"issue":"1","key":"10.1016\/j.jcss.2016.01.005_br0490","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1142\/S0129054108005632","article-title":"A normal form for first-order logic over doubly-linked data structures","volume":"19","author":"Lindell","year":"2008","journal-title":"Int. J. Found. Comput. Sci."},{"issue":"5\u20136","key":"10.1016\/j.jcss.2016.01.005_br0500","doi-asserted-by":"crossref","first-page":"909","DOI":"10.1023\/A:1023027932419","article-title":"Complexity of two-dimensional patterns","volume":"91","author":"Lindgren","year":"1998","journal-title":"J. Stat. Phys."},{"key":"10.1016\/j.jcss.2016.01.005_br0510","series-title":"MFCS","first-page":"751","article-title":"One quantifier will do in existential monadic second-order logic over pictures","author":"Matz","year":"1998"},{"key":"10.1016\/j.jcss.2016.01.005_br0520","series-title":"Logic and Automata: History and Perspectives [in Honor of Wolfgang Thomas]","first-page":"531","article-title":"Expressive power of monadic logics on words, trees, pictures, and graphs","author":"Matz","year":"2008"},{"issue":"2","key":"10.1016\/j.jcss.2016.01.005_br0530","doi-asserted-by":"crossref","first-page":"356","DOI":"10.1006\/inco.2002.2955","article-title":"The monadic quantifier alternation hierarchy over grids and graphs","volume":"179","author":"Matz","year":"2002","journal-title":"Inf. Comput."},{"key":"10.1016\/j.jcss.2016.01.005_br0540","series-title":"LICS","first-page":"236","article-title":"The monadic quantifier alternation hierarchy over graphs is infinite","author":"Matz","year":"1997"},{"key":"10.1016\/j.jcss.2016.01.005_br0550","series-title":"Counter-Free Automata","author":"McNaughton","year":"1971"},{"key":"10.1016\/j.jcss.2016.01.005_br0560","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1002\/malq.19750210118","article-title":"On languages with two variables","volume":"21","author":"Mortimer","year":"1975","journal-title":"Z. Math. Log. Grundl. Math."},{"issue":"6","key":"10.1016\/j.jcss.2016.01.005_br0570","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1016\/0020-0190(94)00219-O","article-title":"A note on the number of monadic quantifiers in monadic \u03a311","volume":"53","author":"Otto","year":"1995","journal-title":"Inf. Process. Lett."},{"issue":"2","key":"10.1016\/j.jcss.2016.01.005_br0580","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1006\/inco.1998.2741","article-title":"Computations on nondeterministic cellular automata","volume":"148","author":"Ozhigov","year":"1999","journal-title":"Inf. Comput."},{"key":"10.1016\/j.jcss.2016.01.005_br0590","series-title":"STACS","first-page":"133","article-title":"Cellular automata: real-time equivalence between one-dimensional neighborhoods","author":"Poupet","year":"2005"},{"key":"10.1016\/j.jcss.2016.01.005_br0600","series-title":"MFCS","first-page":"760","article-title":"On some recognizable picture-languages","author":"Reinhardt","year":"1998"},{"key":"10.1016\/j.jcss.2016.01.005_br0610","series-title":"STACS","first-page":"527","article-title":"The #a=#b pictures are recognizable","author":"Reinhardt","year":"2001"},{"key":"10.1016\/j.jcss.2016.01.005_br0620","series-title":"Handbook of Natural Computing","year":"2012"},{"issue":"3","key":"10.1016\/j.jcss.2016.01.005_br0630","doi-asserted-by":"crossref","first-page":"490","DOI":"10.1137\/0209036","article-title":"Storage modification machines","volume":"9","author":"Sch\u00f6nhage","year":"1980","journal-title":"SIAM J. Comput."},{"key":"10.1016\/j.jcss.2016.01.005_br0640","series-title":"CSL","first-page":"441","article-title":"The monadic quantifier alternation hierarchy over grids and pictures","author":"Schweikardt","year":"1997"},{"issue":"1","key":"10.1016\/j.jcss.2016.01.005_br0650","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1016\/0168-0072(95)00030-5","article-title":"On winning ehrenfeucht games and monadic np","volume":"79","author":"Schwentick","year":"1996","journal-title":"Ann. Pure Appl. Logic"},{"key":"10.1016\/j.jcss.2016.01.005_br0660","series-title":"STACS","first-page":"444","article-title":"Local normal forms for first-order logic with applications to games and automata","volume":"vol. 1373","author":"Schwentick","year":"1998"},{"key":"10.1016\/j.jcss.2016.01.005_br0670","doi-asserted-by":"crossref","first-page":"246","DOI":"10.1016\/S1571-0661(05)80203-8","article-title":"Linear time computable problems and logical descriptions","volume":"2","author":"Seese","year":"1995","journal-title":"Electron. Notes Theor. Comput. Sci."},{"key":"10.1016\/j.jcss.2016.01.005_br0680","doi-asserted-by":"crossref","first-page":"505","DOI":"10.1017\/S0960129500070079","article-title":"Linear time computable problems and first-order descriptions","volume":"6","author":"Seese","year":"1996","journal-title":"Math. Struct. Comput. Sci."},{"issue":"1","key":"10.1016\/j.jcss.2016.01.005_br0690","doi-asserted-by":"crossref","first-page":"146","DOI":"10.1145\/322047.322061","article-title":"Separating nondeterministic time complexity classes","volume":"25","author":"Seiferas","year":"1978","journal-title":"J. ACM"},{"key":"10.1016\/j.jcss.2016.01.005_br0700","doi-asserted-by":"crossref","first-page":"397","DOI":"10.1007\/BF00290736","article-title":"Parallel language recognition in constant time by cellular automata","volume":"19","author":"Sommerhalder","year":"1983","journal-title":"Acta Inform."},{"key":"10.1016\/j.jcss.2016.01.005_br0710","series-title":"Handbook of Natural Computing","first-page":"123","article-title":"Language recognition by cellular automata","volume":"vol. 1","author":"Terrier","year":"2012"},{"issue":"1","key":"10.1016\/j.jcss.2016.01.005_br0720","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1007\/BF01691346","article-title":"Generalized finite automata theory with an application to a decision problem of Second-Order logic","volume":"2","author":"Thatcher","year":"1968","journal-title":"Math. Syst. Theory"},{"issue":"3","key":"10.1016\/j.jcss.2016.01.005_br0730","doi-asserted-by":"crossref","first-page":"360","DOI":"10.1016\/0022-0000(82)90016-2","article-title":"Classifying regular events in symbolic logic","volume":"25","author":"Thomas","year":"1982","journal-title":"J. Comput. Syst. Sci."},{"key":"10.1016\/j.jcss.2016.01.005_br0740","series-title":"ICALP","first-page":"441","article-title":"On logics, tilings, and automata","volume":"vol. 510","author":"Thomas","year":"1991"},{"key":"10.1016\/j.jcss.2016.01.005_br0750","first-page":"103","article-title":"Finite automata and the logic of one-place predicates","volume":"3","author":"Trakhtenbrot","year":"1962","journal-title":"Sib. Math. J."},{"key":"10.1016\/j.jcss.2016.01.005_br0760","series-title":"Proc. 1st GTI Workshop","first-page":"75","article-title":"Dominos are forever","author":"van Emde Boas","year":"1982"},{"key":"10.1016\/j.jcss.2016.01.005_br0770","series-title":"Complexity, Logic and Recursion Theory","first-page":"331","article-title":"The convenience of tilings","volume":"vol. 187","author":"van Emde Boas","year":"1997"},{"key":"10.1016\/j.jcss.2016.01.005_br0780","series-title":"Proceedings of the Symposium on the Mathematical Theory of Automata","first-page":"23","article-title":"Dominoes and the AEA case of the decision problem","author":"Wang","year":"1963"},{"key":"10.1016\/j.jcss.2016.01.005_br0790","series-title":"Computation, Logic, Philosophy. A Collection of Essays","author":"Wang","year":"1990"}],"container-title":["Journal of Computer and System Sciences"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0022000016000258?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0022000016000258?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2020,9,1]],"date-time":"2020-09-01T00:54:59Z","timestamp":1598921699000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0022000016000258"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,9]]},"references-count":77,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2016,9]]}},"alternative-id":["S0022000016000258"],"URL":"https:\/\/doi.org\/10.1016\/j.jcss.2016.01.005","relation":{},"ISSN":["0022-0000"],"issn-type":[{"value":"0022-0000","type":"print"}],"subject":[],"published":{"date-parts":[[2016,9]]},"assertion":[{"value":"Elsevier","name":"publisher","label":"This article is maintained by"},{"value":"A logical approach to locality in pictures languages","name":"articletitle","label":"Article Title"},{"value":"Journal of Computer and System Sciences","name":"journaltitle","label":"Journal Title"},{"value":"https:\/\/doi.org\/10.1016\/j.jcss.2016.01.005","name":"articlelink","label":"CrossRef DOI link to publisher maintained version"},{"value":"article","name":"content_type","label":"Content Type"},{"value":"\u00a9 2016 Elsevier Inc.","name":"copyright","label":"Copyright"}]}}