Finite-state Optimality Theory : non-rationality of Harmonic Serialism

• Autorzy: Hao Yiding

Identyfikatory

DOI

10.15398/jlm.v7i2.210

• Języki publikacji: EN

Abstrakty

EN

This paper analyzes the language-theoretic complexity of Harmonic Serialism (HS), a derivational variant of Optimality Theory. I show that HS can generate non-rational relations using strictly local markedness constraints, proving the “result” of Hao (2017), that HS is rational under those assumptions, to be incorrect. This is possible because deletions performed in a particular order have the ability to enforce nesting dependencies over long distances. I argue that coordinated deletions form a canonical characterization of non-rational relations definable in HS.

Słowa kluczowe

EN

optimality theory; harmonic serialism; phonology; finite-state; strictly local; subregular

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

Twórcy

autor

Hao Yiding

• Department of Linguistics, Department of Computer Science, Yale University, New Haven, Connecticut, USA

Bibliografia

• [1] Parosh Aziz Abdulla, Bengt Jonsson, Marcus Nilsson, and Julien d’Orso (2002), Regular Model Checking Made Simple and Effcient, in Luboš Brim, Mojmír Křetínský, Antonín Kučera, and Petr Jančar, editors, CONCUR 2002-Concurrency Theory: 13th International Conference, Brno, Czech Republic, August 20-23, 2002, Proceedings, volume 2421 of Lecture Notes in Computer Science, pp. 116-131, Springer Berlin Heidelberg, Berlin, Germany, ISBN 978-3-540-45694-0, doi: 10.1007/3-540-45694-5_9.
• [2] Parosh Aziz Abdulla, Bengt Jonsson, Marcus Nilsson, and Julien d’Orso (2003), Algorithmic Improvements in Regular Model Checking, in Warren A. Hunt and Fabio Somenzi, editors, Computer Aided Verification: 15th International Conference, CAV 2003, Boulder, CO, USA, July 8-12, 2003. Proceedings, volume 2725 of Lecture Notes in Computer Science, pp. 236-248, Springer Berlin Heidelberg, Berlin, Germany, ISBN 978-3-540-45069-6, doi: 10.1007/978-3-540-45069-6_25.
• [3] James K. Baker (1975), The DRAGON System-An Overview, IEEE Transactions on Acoustics, Speech, and Signal Processing, 23 (1): 24-29, ISSN 0096-3518, doi: 10.1109/TASSP.1975.1162650.
• [4] Eric Baković (1999), Assimilation to the Unmarked, in Jim Alexander, Alexis Dimitriadis, Na-Rae Han, Elsi Kaiser, Michelle Minnick Fox, Christine Moisset, and Alexander Williams, editors, Proceedings of the 23rd Annual Penn Linguistics Colloquium, volume 6.1 of University of Pennsylvania Working Papers in Linguistics, pp. 1-16, Penn Graduate Linguistics Society, Philadelphia, PA, USA.
• [5] Eric Baković (2000), Harmony, Dominance and Control, PhD dissertation, Rutgers University, New Brunswick, NJ, USA.
• [6] Robert C. Berwick (1984), Strong Generative Capacity, Weak Generative Capacity, and Modern Linguistic Theories, Computational Linguistics, 10 (3-4): 189-202, ISSN 0891-2017.
• [7] Ahmed Bouajjani, Bengt Jonsson, Marcus Nilsson, and Tayssir Touili (2000), Regular Model Checking, in E. Allen Emerson and Aravinda Prasad Sistla, editors, Computer Aided Verification: 12th International Conference, CAV 2000, Chicago, IL, USA, July 15-19, 2000, Proceedings, volume 1855 of Lecture Notes in Computer Science, pp. 403-418, Springer Berlin Heidelberg, Berlin, Germany, ISBN 978-3-540-45047-4, doi: 10.1007/10722167_31.
• [8] Joan Chen-Main and Robert Frank (2003), Implementing Faithfulness Constraints in a Finite State Model of Optimality Theory, in Pádraig Cunningham, Tim Fernando, and Carl Vogel, editors, Proceedings of the 14th Irish Conference on Artificial Intelligence and Cognitive Science, pp. 28-33, Trinity College Dublin, Dublin, Ireland.
• [9] Noam Chomsky (1959), On Certain Formal Properties of Grammars, Information and Control, 2 (2): 137-167, ISSN 0019-9958, doi: 10.1016/S0019-9958(59)90362-6.
• [10] Noam Chomsky and Morris Halle (1968), The Sound Pattern of English, Harper & Row, New York, NY, USA, 1 edition, ISBN 978-0-06-041276-0.
• [11] Dennis Dams, Yassine Lakhnech, and Martin Steffen (2001a), Iterating Transducers, Technical Report TR-ST-01-03, University of Kiel Institut für Informatik und praktische Mathematik, Kiel, Germany.
• [12] Dennis Dams, Yassine Lakhnech, and Martin Steffen (2001b), Iterating Transducers, in Gérard Berry, Hubert Comon, and Alain Finkel, editors, 13th International Conference, CAV 2001, Paris, France, July 18-22, 2001, Proceedings, volume 2102 of Lecture Notes in Computer Science, pp. 286-297, Springer Berlin Heidelberg, Berlin, Germany, ISBN 978-3-540-44585-2, doi: 10.1007/3-540-44585-4_27.
• [13] Dennis Dams, Yassine Lakhnech, and Martin Steffen (2002), Iterating Transducers, The Journal of Logic and Algebraic Programming, 52-53: 109-127, ISSN 1567-8326, doi: 10.1016/S1567-8326(02)00025-5.
• [14] 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, College of Wooster, Wooster, OH, USA.
• [15] Jason Eisner (2000), Directional Constraint Evaluation in Optimality Theory, in Proceedings of the 18th Conference on Computational Linguistics, volume 1, pp. 257-263, Association for Computational Linguistics, Saarbrücken, Germany, ISBN 1-55860-717-X, doi: 10.3115/990820.990858.
• [16] Jason Eisner (2002), Comprehension and Compilation in Optimality Theory, in Proceedings of 40th Annual Meeting of the Association for Computational Linguistics, pp. 56-63, Association for Computational Linguistics, Philadelphia, PA, USA, doi: 10.3115/1073083.1073095.
• [17] Emily Elfner (2009), Syllabification and Stress-Epenthesis Interactions in Harmonic Serialism, Rutgers Optimality Archive, ROA-1047.
• [18] Emily Elfner (2016), Stress-Epenthesis Interactions in Harmonic Serialism, in John J. McCarthy, Joe Pater, Vieri Samek-Lodovici, and Armin Mester, editors, Harmonic Grammar and Harmonic Serialism, Advances in Optimality Theory, pp. 261-300, Equinox Publishing, Sheffield, United Kingdom, ISBN 978-1-84553-149-2.
• [19] T. Mark Ellison (1994), Phonological Derivation in Optimality Theory, in Proceedings of the 15th Conference on Computational Linguistics, volume 2, pp. 1007-1013, Association for Computational Linguistics, Kyoto, Japan, doi: 10.3115/991250.991312.
• [20] Robert Frank and Giorgio Satta (1998), Optimality Theory and the Generative Complexity of Constraint Violability, Computational Linguistics, 24 (2): 307-315, ISSN 0891-2017.
• [21] Dale Gerdemann and Mans Hulden (2012), Practical Finite State Optimality Theory, in Proceedings of the 10th International Workshop on Finite State Methods and Natural Language Processing, pp. 10-19, Association for Computational Linguistics, San Sebastián, Spain.
• [22] Dale Gerdemann and Gertjan van Noord (2000), Approximation and Exactness in Finite State Optimality Theory, in Jason Eisner, Lauri Karttunen, and Alain Thériault, editors, Finite-State Phonlogy: Proceedings of the Fifth Workshop on the ACL Special Interest Group in Computational Phonology, pp. 34-45, Association for Computational Linguistics, Luxembourg City, Luxembourg.
• [23] Kenneth Hale (1973), Deep-Surface Canonical Disparities in Relation to Analysis and Change: An Australian Example, in Thomas A. Sebeok, editor, Current Trends in Linguistics, volume 8: Linguistics in Oceania, pp. 401-458, Mouton, The Hague, Netherlands.
• [24] Yiding Hao (2017), Harmonic Serialism and Finite-State Optimality Theory, in Frank Drewes, editor, Proceedings of the 13th International Conference on Finite State Methods and Natural Language Processing, pp. 20-29, Association for Computational Linguistics, Umeå, Sweden, doi: 10.18653/v1/W17-4003.
• [25] Jeffrey Heinz (2009), On the Role of Locality in Learning Stress Patterns, Phonology, 26 (2): 303-351, ISSN 0952-6757, doi: 10.1017/S0952675709990145.
• [26] Jeffrey Heinz (2014), Culminativity Times Harmony Equals Unbounded Stress, in Harry van der Hulst, editor, Word Stress: Theoretical and Typological Issues, pp. 255-275, Cambridge University Press, Cambridge, United Kingdom, ISBN 978-1-107-03951-3, doi: 10.1017/CBO9781139600408.012.
• [27] Jeffrey Heinz, Chetan Rawal, and Herbert G. Tanner (2011), Tier-Based Strictly Local Constraints for Phonology, in Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies, pp. 58-64, Association for Computational Linguistics, Portland, OR, USA.
• [28] Jeffrey Nicholas Heinz (2007), Inductive Learning of Phonotactic Patterns, PhD dissertation, University of California, Los Angeles, Los Angeles, CA, USA.
• [29] Patrick W. Hohepa (1967), A Profile Generative Grammar of Maori, number 20 in Indiana University Publications in Anthropology and Linguistics, Waverly Press, Baltimore, MD, USA.
• [30] Frederick Jelinek (1976), Continuous Speech Recognition by Statistical Methods, Proceedings of the IEEE, 64 (4): 532-556, ISSN 0018-9219, doi: 10.1109/PROC.1976.10159.
• [31] C. Douglas Johnson (1970), Formal Aspects of Phonological Description, PhD dissertation, University of California, Berkeley, Berkeley, CA, USA.
• [32] C. Douglas Johnson (1972), Formal Aspects of Phonological Description, Mouton, The Hague, Netherlands.
• [33] Bengt Jonsson and Marcus Nilsson (2000), Transitive Closures of Regular Relations for Verifying Infinite-State Systems, in Susanne Graf and Michael Schwartzbach, editors, 6th International Conference, TACAS 2000, Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2000, Berlin, Germany, March 25-April 2, 2000, Proceedings, volume 1785 of Lecture Notes in Computer Science, pp. 220-235, Springer Berlin Heidelberg, Berlin, Germany, ISBN 978-3-540-46419-8, doi: 10.1007/3-540-46419-0_16.
• [34] Ronald M. Kaplan and Martin Kay (1994), Regular Models of Phonological Rule Systems, Computational Linguistics, 20 (3): 331-378, ISSN 0891-2017.
• [35] Lauri Karttunen (1998), The Proper Treatment of Optimality in Computational Phonology, in Proceedings of the International Workshop on Finite State Methods in Natural Language Processing, pp. 1-12, Association for Computational Linguistics, Ankara, Turkey.
• [36] Regine Lai (2015), Learnable vs. Unlearnable Harmony Patterns, Linguistic Inquiry, 46 (3): 425-451, ISSN 0024-3892, doi: 10.1162/LING_a_00188.
• [37] Yeeking Regine Lai (2012), Domain Specificity in Learning Phonology, PhD dissertation, University of Delaware, Newark, DE, USA.
• [38] Andrew Lamont (2018a), Precedence Is Pathological, conference presentation at Phonology in the Northeast, Cambridge, MA, USA.
• [39] Andrew Lamont (2018b), Precedence Is Pathological: The Problem of Alphabetical Sorting, conference presentation at the West Coast Conference on Formal Linguistics, Los Angeles, CA, USA.
• [40] Bruce T. Lowerre (1976), The HARPY Speech Recognition System, PhD dissertation, Carnegie-Mellon University, Pittsburgh, PA, USA.
• [41] John J. McCarthy (2007), Hidden Generalizations: Phonological Opacity in Optimality Theory, Advances in Optimality Theory, Equinox Publishing, Sheffield, United Kingdom, ISBN 978-1-84553-051-8.
• [42] John J. McCarthy (2008), The Serial Interaction of Stress and Syncope, Natural Language & Linguistic Theory, 26 (3): 499-546, ISSN 1573-0859, doi: 10.1007/s11049-008-9051-3.
• [43] John J. McCarthy (2009), Harmony in Harmonic Serialism, Rutgers Optimality Archive, ROA-1009.
• [44] John J. McCarthy (2010), An Introduction to Harmonic Serialism, Language and Linguistics Compass, 4 (10): 1001-1018, ISSN 1749-818X, doi: 10.1111/j.1749-818X.2010.00240.x.
• [45] John J. McCarthy and Alan Prince (1994), The Emergence of the Unmarked: Optimality in Prosodic Morphology, in Mercè Gonzàlez, editor, Proceedings of the North East Linguistics Society 24, pp. 333-379, GLSA Publications, Amherst, MA, USA.
• [46] John J. McCarthy and Alan Prince (1995), Faithfulness and Reduplicative Identity, University of Massachusetts Occasional Papers in Linguistics, 18: Papers in Optimality Theory: 249-384.
• [47] Kevin McMullin and Gunnar Ólafur Hansson (2016), Long-Distance Phonotactics as Tier-Based Strictly 2-Local Languages, in Proceedings of the 2014 Annual Meeting on Phonology, Proceedings of the Annual Meetings on Phonology, pp. 13-24, Linguistic Society of America, Cambridge, MA, USA, doi: 10.3765/amp.v2i0.3750.
• [48] Kevin James McMullin (2016), Tier-Based Locality in Long-Distance Phonotactics: Learnability and Typology, Ph.D. thesis, University of British Columbia, Vancouver, Canada.
• [49] Robert McNaughton and Seymour A. Papert (1971), Counter-Free Automata, number 65 in Research Monograph, MIT Press, Cambridge, MA, USA, ISBN 978-0-262-13076-9.
• [50] Elliott Moreton (1999), Non-Computable Functions in Optimality Theory, Rutgers Optimality Archive, ROA-364.
• [51] Elliott Moreton (2004), Non-Computable Functions in Optimality Theory, in John J. McCarthy, editor, Optimality Theory in Phonology: A Reader, pp. 141-164, Blackwell Publishing, Oxford, United Kingdom, ISBN 978-0-470-75617-1, doi: 10.1002/9780470756171.ch6.
• [52] Joe Pater (2009), Weighted Constraints in Generative Linguistics, Cognitive Science, 33 (6): 999-1035, ISSN 1551-6709, doi: 10.1111/j.1551-6709.2009.01047.x.
• [53] Christopher Potts, Joe Pater, Karen Jesney, Rajesh Bhatt, and Michael Becker (2010), Harmonic Grammar with Linear Programming: From Linear Systems to Linguistic Typology, Phonology, 27 (1): 77-117, ISSN 1469-8188, doi: 10.1017/S0952675710000047.
• [54] Alan Prince (2002), Arguing Optimality, Rutgers Optimality Archive, ROA-562.
• [55] Alan Prince (2003), Arguing Optimality, University of Massachusetts Occasional Papers in Linguistics, 26.
• [56] Alan Prince and Paul Smolensky (1993), Optimality Theory: Constraint Interaction in Generative Grammar, Technical Report 2, Rutgers University, New Brunswick, NJ, USA.
• [57] Alan Prince and Paul Smolensky (2004), Optimality Theory: Constraint Interaction in Generative Grammar, Blackwell Publishing, Malden, MA, USA, ISBN 978-1-4051-1932-0.
• [58] Kathryn Pruitt (2008), Iterative Foot Optimization and Locality in Stress Systems, Rutgers Optimality Archive, ROA-999.
• [59] Kathryn Ringler Pruitt (2012), Stress in Harmonic Serialism, PhD dissertation, University of Massachusetts Amherst, Amherst, MA, USA.
• [60] Jason Alan Riggle (2004), Generation, Recognition, and Learning in Finite State Optimality Theory, PhD dissertation, University of California, Los Angeles, Los Angeles, CA, USA.
• [61] James Rogers and Geoffrey K. Pullum (2011), Aural Pattern Recognition Experiments and the Subregular Hierarchy, Journal of Logic, Language and Information, 20 (3): 329-342, ISSN 1572-9583, doi: 10.1007/s10849-011-9140-2.
• [62] Vieri Samek-Lodovici and Alan Prince (1999), Optima, Rutgers Optimality Archive, ROA-363.
• [63] Vieri Samek-Lodovici and Alan Prince (2002), The Fundamental Properties of Harmonic Bounding, Technical Report TR-71, Rutgers Center for Cognitive Science, Piscataway, NJ, USA.
• [64] Michael Sipser (2013), Introduction to the Theory of Computation, Cengage Learning, Boston, MA, USA, 3 edition, ISBN 978-1-133-18781-3.
• [65] Rachel Walker (2008), Gradualness and Fell-Swoop Derivations, conference presentation at the UCSC Graduate Alumni Conference, Santa Cruz, CA, USA.
• [66] Rachel Walker (2010), Nonmyopic Harmony and the Nature of Derivations, Linguistic Inquiry, 41 (1): 169-179, ISSN 00243892, doi: 10.1162/ling.2010.41.1.169.

Uwagi

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