{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:22:13Z","timestamp":1740122533179,"version":"3.37.3"},"reference-count":38,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2023,5,19]],"date-time":"2023-05-19T00:00:00Z","timestamp":1684454400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,5,19]],"date-time":"2023-05-19T00:00:00Z","timestamp":1684454400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J of Log Lang and Inf"],"published-print":{"date-parts":[[2023,10]]},"DOI":"10.1007\/s10849-023-09398-x","type":"journal-article","created":{"date-parts":[[2023,5,19]],"date-time":"2023-05-19T11:02:31Z","timestamp":1684494151000},"page":"707-731","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Relativized Adjacency"],"prefix":"10.1007","volume":"32","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7056-5950","authenticated-orcid":false,"given":"Dakotah","family":"Lambert","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,5,19]]},"reference":[{"issue":"2","key":"9398_CR1","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1137\/0201008","volume":"1","author":"AV Aho","year":"1972","unstructured":"Aho, A. V., Garey, M. R., & Ullman, J. D. (1972). The transitive reduction of a directed graph. SIAM Journal on Computing, 1(2), 131\u2013137. https:\/\/doi.org\/10.1137\/0201008","journal-title":"SIAM Journal on Computing"},{"key":"9398_CR2","doi-asserted-by":"publisher","unstructured":"Aks\u00ebnova, A., Deshmukh, S. (2018). Formal restrictions on multiple tiers. In Proceedings of the Society for Computation in Linguistics, Salt Lake City, Utah, 1, 64\u201373. https:\/\/doi.org\/10.7275\/R5K64G8S","DOI":"10.7275\/R5K64G8S"},{"key":"9398_CR3","doi-asserted-by":"publisher","unstructured":"Beauquier, D., Pin, J.-E. (1989). Factors of words. In G.\u00a0Ausiello, M.\u00a0Dezani-Ciancaglini, S.\u00a0Ronchi Della\u00a0Rocca (Eds.) Automata, languages and programming: 16th International Colloquium, Lecture Notes in Computer Science, vol 372, Springer Berlin\/Heidelberg (pp. 63\u201379), https:\/\/doi.org\/10.1007\/BFb0035752","DOI":"10.1007\/BFb0035752"},{"key":"9398_CR4","volume-title":"Finite state morphology","author":"KR Beesley","year":"2003","unstructured":"Beesley, K. R., & Karttunen, L. (2003). Finite state morphology. CSLI Publications."},{"issue":"3","key":"9398_CR5","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1016\/S0012-365X(73)80005-6","volume":"4","author":"JA Brzozowski","year":"1973","unstructured":"Brzozowski, J. A., & Simon, I. (1973). Characterizations of locally testable events. Discrete Mathematics, 4(3), 243\u2013271. https:\/\/doi.org\/10.1016\/S0012-365X(73)80005-6","journal-title":"Discrete Mathematics"},{"key":"9398_CR6","doi-asserted-by":"publisher","unstructured":"Caron, P. (1998). LANGAGE: A maple package for automaton characterization of regular languages. In D.\u00a0Wood, S.\u00a0Yu (Eds.) Automata implementation, lecture notes in computer science, vol 1436, Springer Berlin\/Heidelberg (pp. 46\u201355), https:\/\/doi.org\/10.1007\/BFb0031380","DOI":"10.1007\/BFb0031380"},{"key":"9398_CR7","doi-asserted-by":"crossref","unstructured":"Chandlee, J. (2014). Strictly local phonological processes. PhD thesis, University of Delaware, https:\/\/chandlee.sites.haverford.edu\/wp-content\/uploads\/2015\/05\/Chandlee_dissertation_2014.pdf","DOI":"10.3765\/exabs.v0i0.2406"},{"key":"9398_CR8","doi-asserted-by":"publisher","unstructured":"Cser, A. (2010). The -alis\/-aris allomorphy revisited. In F.\u00a0Rainer, W.\u00a0Dressler, D.\u00a0Kastovsky, H.\u00a0C. Lusch\u00fctzky (Eds.) Variation and Change in Morphology: Selected Papers from the 13th International Morphology Meeting, John Benjamins Publishing Company, Vienna, Austria (pp. 33\u201352), https:\/\/doi.org\/10.1075\/cilt.310.02cse","DOI":"10.1075\/cilt.310.02cse"},{"issue":"3","key":"9398_CR9","doi-asserted-by":"publisher","first-page":"300","DOI":"10.1016\/S0019-9958(80)90180-1","volume":"44","author":"A De Luca","year":"1980","unstructured":"De Luca, A., & Restivo, A. (1980). A characterization of strictly locally testable languages and its application to subsemigroups of a free semigroup. Information and Control, 44(3), 300\u2013319. https:\/\/doi.org\/10.1016\/S0019-9958(80)90180-1","journal-title":"Information and Control"},{"key":"9398_CR10","doi-asserted-by":"publisher","unstructured":"De\u00a0Santo, A., Graf, T. (2019). Structure sensitive tier projection: Applications and formal properties. In R.\u00a0Bernardi, G.\u00a0Kobele, S.\u00a0Pogodalla (Eds.) Formal Grammar 2019, lecture notes in computer science, vol 11668, Springer Verlag (pp. 35\u201350), https:\/\/doi.org\/10.1007\/978-3-662-59648-7_3","DOI":"10.1007\/978-3-662-59648-7_3"},{"key":"#cr-split#-9398_CR11.1","unstructured":"Edlefsen, M., Leeman, D., Myers, N., Smith, N., Visscher, M., Wellcome, D. (2008). Deciding strictly local"},{"key":"#cr-split#-9398_CR11.2","unstructured":"(SL) languages. In J.\u00a0Breitenbucher (Ed.) Proceedings of the 2008 Midstates Conference for Undergraduate Research in Computer Science and Mathematics, (pp. 66-73)."},{"issue":"5","key":"9398_CR12","doi-asserted-by":"publisher","first-page":"447","DOI":"10.1016\/S0019-9958(67)91165-5","volume":"10","author":"EM Gold","year":"1967","unstructured":"Gold, E. M. (1967). Language identification in the limit. Information and Control, 10(5), 447\u2013474. https:\/\/doi.org\/10.1016\/S0019-9958(67)91165-5","journal-title":"Information and Control"},{"issue":"2","key":"9398_CR13","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1017\/S0952675717000197","volume":"34","author":"T Graf","year":"2017","unstructured":"Graf, T. (2017). The power of locality domains in phonology. Phonology, 34(2), 385\u2013405. https:\/\/doi.org\/10.1017\/S0952675717000197","journal-title":"Phonology"},{"issue":"1","key":"9398_CR14","doi-asserted-by":"publisher","first-page":"94","DOI":"10.1016\/s0021-9800(69)80111-0","volume":"6","author":"LH Haines","year":"1969","unstructured":"Haines, L. H. (1969). On free monoids partially ordered by embedding. Journal of Combinatorial Theory, 6(1), 94\u201398. https:\/\/doi.org\/10.1016\/s0021-9800(69)80111-0","journal-title":"Journal of Combinatorial Theory"},{"key":"9398_CR15","unstructured":"Heinz, J., Rawal, C., Tanner, H.\u00a0G. (2011). Tier-based strictly local constraints for phonology. In Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Short Papers, Association for Computational Linguistics, Portland, Oregon, 2, 58\u201364, https:\/\/aclweb.org\/anthology\/P11-2011"},{"key":"9398_CR16","unstructured":"Hulden, M. (2009). Finite-state machine construction methods and algorithms for phonology and morphology. PhD thesis, The University of Arizona."},{"key":"9398_CR17","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1162\/tacl\\_a_00085","volume":"4","author":"A Jardine","year":"2016","unstructured":"Jardine, A., & Heinz, J. (2016). Learning tier-based strictly 2-local languages. Transactions of the Association for Computation in Linguistics, 4, 87\u201398. https:\/\/doi.org\/10.1162\/tacl_a_00085","journal-title":"Transactions of the Association for Computation in Linguistics"},{"key":"9398_CR18","doi-asserted-by":"publisher","unstructured":"Jardine, A., McMullin, K. (2017). Efficient learning of tier-based strictly k-local languages. In F.\u00a0Drewes, C.\u00a0Mart\u00edn-Vide, B.\u00a0Truthe (Eds.) Language and automata theory and applications: 11th international conference, lecture notes in computer science, vol 10168, Springer, Cham (pp. 64\u201376), https:\/\/doi.org\/10.1007\/978-3-319-53733-7_4","DOI":"10.1007\/978-3-319-53733-7_4"},{"key":"9398_CR19","doi-asserted-by":"publisher","unstructured":"Ji, J., Heinz, J. (2020). Input strictly local tree transducers. In A.\u00a0Leporati, C.\u00a0Mart\u00edn-Vide, D.\u00a0Shapira, C.\u00a0Zandron (Eds.) Language and automata theory and applications. In Proceedings of the 14th international conference, LATA 2020, Springer International Publishing, Cham, Switzerland, Theoretical Computer Science and General Issues, vol 12038, (pp. 369\u2013381), https:\/\/doi.org\/10.1007\/978-3-030-40608-0_26","DOI":"10.1007\/978-3-030-40608-0_26"},{"issue":"2","key":"9398_CR20","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1137\/0206024","volume":"6","author":"DE Knuth","year":"1977","unstructured":"Knuth, D. E., Morris, J. H., & Pratt, V. R. (1977). Fast pattern matching in strings. SIAM Journal on Computing, 6(2), 323\u2013350. https:\/\/doi.org\/10.1137\/0206024","journal-title":"SIAM Journal on Computing"},{"key":"9398_CR21","doi-asserted-by":"publisher","unstructured":"Lambert, D., Rogers, J. (2020). Tier-based strictly local stringsets: Perspectives from model and automata theory. In Proceedings of the society for computation in linguistics, New Orleans, Louisiana, 3, 330\u2013337, https:\/\/doi.org\/10.7275\/2n1j-pj39","DOI":"10.7275\/2n1j-pj39"},{"key":"9398_CR22","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-07003-1","author":"L Libkin","year":"2004","unstructured":"Libkin, L. (2004). Elements of finite model theory. Texts in Theoretical Computer Science. https:\/\/doi.org\/10.1007\/978-3-662-07003-1","journal-title":"Texts in Theoretical Computer Science"},{"key":"9398_CR23","unstructured":"McMullin, K. (2016). Tier-based locality in long-distance phonotactics: Learnability and typology. PhD thesis, University of British Columbia."},{"issue":"1","key":"9398_CR24","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1007\/bf01761708","volume":"8","author":"R McNaughton","year":"1974","unstructured":"McNaughton, R. (1974). Algebraic decision procedures for local testability. Mathematical Systems Theory, 8(1), 60\u201376. https:\/\/doi.org\/10.1007\/bf01761708","journal-title":"Mathematical Systems Theory"},{"key":"9398_CR25","volume-title":"Counter-free automata","author":"R McNaughton","year":"1971","unstructured":"McNaughton, R., & Papert, S. A. (1971). Counter-free automata. MIT Press."},{"key":"9398_CR26","doi-asserted-by":"publisher","unstructured":"Nerode, A. (1958). Linear automaton transformations. In Proceedings of the American Mathematical Society, American Mathematical Society, 9, 541\u2013544, https:\/\/doi.org\/10.1090\/s0002-9939-1958-0135681-9","DOI":"10.1090\/s0002-9939-1958-0135681-9"},{"key":"9398_CR27","doi-asserted-by":"publisher","unstructured":"Pin, J.-E. (1997). Syntactic semigroups. In G.\u00a0Rozenberg, A.\u00a0Salomaa (Eds.) Handbook of Formal Languages: Volume 1 Word, Language, Grammar, Springer-Verlag, Berlin (pp. 679\u2013746), https:\/\/doi.org\/10.1007\/978-3-642-59136-5_10","DOI":"10.1007\/978-3-642-59136-5_10"},{"key":"9398_CR28","doi-asserted-by":"publisher","unstructured":"Rogers, J. (1996). A model-theoretic framework for theories of syntax. In Proceedings of the 34th Annual Meeting of the Association for Computational Linguistics, Association for Computational Linguistics, Santa Cruz, CA, (pp. 10\u201316), https:\/\/doi.org\/10.3115\/981863.981865","DOI":"10.3115\/981863.981865"},{"key":"9398_CR29","doi-asserted-by":"publisher","unstructured":"Rogers, J. (1997). Strict LT$${}_2$$ : regular : local : recognizable. In C.\u00a0Retor\u00e9 (Ed.) Logical aspects of computational linguistics: first international conference, LACL \u201996 (Selected Papers), Springer-Verlag, Berlin, Lecture Notes in Computer Science, vol 1328, (pp. 366\u2013385), https:\/\/doi.org\/10.1007\/BFb0052167","DOI":"10.1007\/BFb0052167"},{"key":"9398_CR30","unstructured":"Rogers, J. (1998). A descriptive approach to language-theoretic complexity. (Monograph.) Studies in Logic, Language, and Information, CSLI Publications."},{"issue":"2","key":"9398_CR31","doi-asserted-by":"publisher","first-page":"143","DOI":"10.15398\/jlm.v7i2.209","volume":"7","author":"J Rogers","year":"2019","unstructured":"Rogers, J., & Lambert, D. (2019). Extracting Subregular constraints from Regular stringsets. Journal of Language Modelling, 7(2), 143\u2013176. https:\/\/doi.org\/10.15398\/jlm.v7i2.209","journal-title":"Journal of Language Modelling"},{"key":"9398_CR32","doi-asserted-by":"publisher","unstructured":"Rogers, J., Lambert, D. (2019b). Some classes of sets of structures definable without quantifiers. In Proceedings of the 16th Meeting on the Mathematics of Language, Association for Computational Linguistics, Toronto, Canada, (pp. 63\u201377), https:\/\/doi.org\/10.18653\/v1\/W19-5706","DOI":"10.18653\/v1\/W19-5706"},{"issue":"3","key":"9398_CR33","doi-asserted-by":"publisher","first-page":"329","DOI":"10.1007\/s10849-011-9140-2","volume":"20","author":"J Rogers","year":"2011","unstructured":"Rogers, J., & Pullum, G. K. (2011). Aural pattern recognition experiments and the subregular hierarchy. Journal of Logic, Language and Information, 20(3), 329\u2013342. https:\/\/doi.org\/10.1007\/s10849-011-9140-2","journal-title":"Journal of Logic, Language and Information"},{"key":"9398_CR34","doi-asserted-by":"publisher","unstructured":"Rogers, J., Heinz, J., Bailey, G., Edlefsen, M., Visscher, M., Wellcome, D., Wibel, S. (2010). On languages piecewise testable in the strict sense. In C.\u00a0Ebert, G.\u00a0J\u00e4ger, J.\u00a0Michaelis (Eds.) The mathematics of language: Revised selected papers from the 10th and 11th biennial conference on the mathematics of language, LNCS\/LNAI, vol 6149, FoLLI\/Springer (pp. 255\u2013265), https:\/\/doi.org\/10.1007\/978-3-642-14322-9_19","DOI":"10.1007\/978-3-642-14322-9_19"},{"issue":"2","key":"9398_CR35","doi-asserted-by":"publisher","first-page":"190","DOI":"10.1016\/s0019-9958(65)90108-7","volume":"8","author":"M-P Sch\u00fctzenberger","year":"1965","unstructured":"Sch\u00fctzenberger, M.-P. (1965). On finite monoids having only trivial subgroups. Information and Control, 8(2), 190\u2013194. https:\/\/doi.org\/10.1016\/s0019-9958(65)90108-7","journal-title":"Information and Control"},{"key":"9398_CR36","first-page":"245","volume":"15","author":"M-P Sch\u00fctzenberger","year":"1975","unstructured":"Sch\u00fctzenberger, M.-P. (1975). Sur certaines op\u00e9rations de fermeture dans les langages rationnels. Symposia Mathematica, 15, 245\u2013253.","journal-title":"Symposia Mathematica"},{"key":"9398_CR37","doi-asserted-by":"publisher","unstructured":"Simon, I. (1975). Piecewise testable events. In H.\u00a0Brakhage (Ed.) Automata theory and formal languages, lecture notes in computer science, vol\u00a033, Springer-Verlag, Berlin (pp. 214\u2013222), https:\/\/doi.org\/10.1007\/3-540-07407-4_23","DOI":"10.1007\/3-540-07407-4_23"}],"container-title":["Journal of Logic, Language and Information"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10849-023-09398-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10849-023-09398-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10849-023-09398-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,8,30]],"date-time":"2023-08-30T12:07:07Z","timestamp":1693397227000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10849-023-09398-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,5,19]]},"references-count":38,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2023,10]]}},"alternative-id":["9398"],"URL":"https:\/\/doi.org\/10.1007\/s10849-023-09398-x","relation":{},"ISSN":["0925-8531","1572-9583"],"issn-type":[{"type":"print","value":"0925-8531"},{"type":"electronic","value":"1572-9583"}],"subject":[],"published":{"date-parts":[[2023,5,19]]},"assertion":[{"value":"5 April 2023","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 May 2023","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The author has no conflicts of interest to declare that are relevant to the content of this article.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}