Extracting Subregular constraints from Regular stringsets

• Autorzy: Rogers James , Lambert Dakotah

Identyfikatory

DOI

10.15398/jlm.v7i2.209

• Języki publikacji: EN

Abstrakty

EN

We introduce algorithms that, given a finite-state automaton (FSA), compute a minimal set of forbidden local factors that define a Strictly Local (SL) tight approximation of the stringset recognised by the FSA and the set of forbidden piecewise factors that define a Strictly Piecewise (SP) tight approximation of that stringset, as well as a set of co-SL factors that, together with the SL and SP factors, provide a set of purely conjunctive literal constraints defining a minimal superset of the stringset recognised by the automaton. Using these, we have built computational tools that have allowed us to reproduce, by nearly purely computational means, the work of Rogers and his co-workers (Rogers et al. 2012) in which, using a mix of computational and analytical techniques, they completely characterised, with respect to the Local and Piecewise Subregular hierarchies, the constraints on the distribution of stress in human languages that are documented in the StressTyp2 database. Our focus, in this paper, is on the algorithms and the method of their application. The phonology of stress patterns is a particularly good domain of application since, as we show here, they generally fall at the very lowest levels of complexity. We discuss these phonological results here, but do not consider their consequences in depth.

Słowa kluczowe

EN

regular languages; finite-state automata; local languages; piecewise languages

• Wydawca: Instytut Podstaw Informatyki PAN
• Czasopismo: Journal of Language Modelling
• Rocznik: 2019
• Tom: Vol. 7, No. 2
• Strony: 143--176
• Opis fizyczny: Bibliogr. 24 poz., rys.

Twórcy

autor

Rogers James

• Dept. of Computer Science, Earlham College, Richmond, IN, USA

autor

Lambert Dakotah

• Dept. of Computer Science, Earlham College, Richmond, IN, USA

Bibliografia

• [1] Pascal Caron (2000), Families of locally testable languages, Theoretical Computer Science, 242: 361-376.
• [2] Jane Chandlee (2014), Strictly local phonological processes, Ph.D. thesis, University of Delaware.
• [3] François Denis, Aurélien Lemay, and Alain Terlutte (2002), Residual finite state automata, Fundamenta Informaticae, 51 (4): 339-368.
• [4] Matt Edlefsen, Dylan Leeman, Nathan Myers, Nathaniel Smith, Molly Visscher, and David Wellcome (2008), Deciding strictly local (SL) languages, in Jon Breitenbucher, editor, Proceedings of the Midstates Conference for Undergraduate Research in Computer Science and Mathematics, pp. 66-73.
• [5] Margaret Fero, Dakotah Lambert, Sean Wibel, and James Rogers (2014), Abstract categories of phonotactic constraints, https://apps.cur.org/ncur2018/archive/Display_NCUR.aspx?id=83628, Retrieved 30 January 2018, presented at the National Conference on Undergraduate Research (NCUR’14).
• [6] Jie Fu, Jeffrey Heinz, and Herbert G. Tanner (2011), An algebraic characterization of strictly piecewise languages, in Mitsunori Ogihara and Jun Tarui, editors, Theory and applications of models of computation, volume 6648 of Lecture Notes in Computer Science, pp. 252-263, Springer, Berlin.
• [7] R. W. N. Goedemans, Jeffrey Heinz, and Harry van der Hulst (2015), StressTyp2, http://st2.ullet.net/, retrieved 30 January 2018.
• [8] Jeffrey Heinz (2010), Learning long-distance phonotactics, Linguistic Inquiry, 41 (4): 623-661.
• [9] Jeffrey Heinz (2018), The computational nature of phonological generalizations, in Larry Hyman and Frank Plank, editors, Phonological typology, volume 23 of Phonetics and Phonology, chapter 5, pp. 126-195, Mouton De Gruyter, Berlin.
• [10] John E. Hopcroft and Jeffrey D. Ullman (1979), Introduction to automata theory, languages and computation, Addison-Wesley, Boston, MA.
• [11] Larry M. Hyman (2009), How (not) to do phonological typology: the case of pitch-accent, Language Sciences, 31 (2-3): 213-238.
• [12] Adam Jardine (2016), Locality and non-linear representations in tonal phonology, Ph.D. thesis, University of Delaware.
• [13] M. Lothaire, editor (1983), Combinatorics on words, Cambridge University Press, New York.
• [14] Robert McNaughton and Seymour Papert (1971), Counter-free automata, MIT Press, Cambridge, MA.
• [15] Mark-Jan Nederhof (2000), Practical experiments with regular approximation of context-free languages, Computational Linguistics, 26 (1). http://aclweb.org/anthology/J00-1003.
• [16] Geofforey K. Pullum and Barbara C. Scholz (2001), On the distinction between model-theoretic and generative-enumerative syntactic frameworks, in Philippe de Groote, Glyn Morrill, and Christian Retoré, editors, Logical Aspects of Computational Linguistics: 4th international conference, volume 2099 of Lecture Notes in Artificial Intelligence, pp. 17-43, Springer Verlag, Berlin.
• [17] James Rogers (1994), Capturing CFLs with tree adjoining grammars, in Proceedings of the 32nd Annual Meeting of the Association for Computational Linguistics (ACL’94), pp. 155-162, Association for Computational Linguistics, Las Cruces, NM.
• [18] James Rogers (1996), A model-theoretic framework for theories of syntax, in Proceedings of the 34th Annual Meeting of the Association for Computational Linguistics (ACL’96), pp. 10-16, Association for Computational Linguistics, Santa Cruz, CA.
• [19] James Rogers, Jeff Heinz, Margaret Fero, Jeremy Hurst, Dakotah Lambert, and Sean Wibel (2012), Cognitive and sub-regular complexity, in Glyn Morrill and Mark-Jan Nederhof, editors, Formal Grammar 2012, volume 8036 of Lecture Notes in Computer Science, pp. 90-108, Springer, Berlin.
• [20] James Rogers, Jeffrey Heinz, Gil Bailey, Matt Edlefsen, Molly Visscher, David Wellcome, and Sean Wibel (2010), On languages piecewise testable in the strict sense, in Christian Ebert, Gerhard Jäger, and Jens Michaelis, editors, The mathematics of language: revised selected papers from the 10th and 11th biennial conference on the mathematics of language, volume 6149 of Lecture Notes in Artificial Intelligence, pp. 255-265, FoLLI/Springer, Berlin.
• [21] Geoffrey Sampson (1975), The form of language, Weidenfeld and Nicolson, London.
• [22] Yves Schabes and Richard C. Waters (1993), Lexicalized context-free grammars, in Proceedings of the 31st Annual Meeting of the Association for Computational Linguistics (ACL’93), pp. 121-129, Association for Computational Linguistics, Columbus, OH.
• [23] Imre Simon (1975), Piecewise testable events, in Helmut Brakhage, editor, Automata theory and formal languages, volume 33 of Lecture Notes in Computer Science, pp. 214-222, Springer Verlag, Berlin.
• [24] Wolfgang Thomas (1982), Classifying regular events in symbolic logic, Journal of Computer and Systems Sciences, 25 (3): 360-376.

Uwagi

Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2020).