On regular copying languages

Wang, Yang; Hunter, Tim

doi:10.15398/jlm.v11i1.342

Artykuł - szczegóły

Tytuł artykułu

On regular copying languages

Autorzy

Wang Yang , Hunter Tim

Treść / Zawartość

Pełne teksty:

Pobierz

Identyfikatory

DOI

10.15398/jlm.v11i1.342

Warianty tytułu

Języki publikacji

Abstrakty

This paper proposes a formal model of regular languages enriched with unbounded copying. We augment finite-state machinery with the ability to recognize copied strings by adding an unbounded memory buffer with a restricted form of first-in-first-out storage. The newly introduced computational device, finite-state buffered machines (FS-BMs), characterizes the class of regular languages and languages de-rived from them through a primitive copying operation. We name this language class regular copying languages (RCLs). We prove a pumping lemma and examine the closure properties of this language class. As suggested by previous literature (Gazdar and Pullum 1985, p.278), regular copying languages should approach the correct characteriza-tion of natural language word sets.

Słowa kluczowe

reduplication copying finite-state machinery queue automata

Wydawca

Instytut Podstaw Informatyki PAN

Czasopismo

Journal of Language Modelling

Rocznik

2023

Tom

Vol. 11, No. 1

Strony

1--66

Opis fizyczny

Bibliogr. 87 poz., rys., tab.

Twórcy

autor

Wang Yang

yangwangx@g.ucla.edu

University of California, Los Angeles

https://orcid.org/0000-0003-0575-2626+

autor

Hunter Tim

timhunter@ucla.edu

University of California, Los Angeles

https://orcid.org/0000-0003-1587-9049+

Bibliografia

1. Daniel M. ALBRO (1998), Evaluation, implementation, and extension of primitive optimality theory, Master’s thesis, University of California, Los Angeles.
2. John ALDERETE, Jill BECKMAN, Laura BENUA, Amalia GNANADESIKAN, John MCCARTHY, and Suzanne URBANCZYK (1999), Reduplication with fixed segmentism, Linguistic Inquiry, 30(3):327–364, https://doi.org/10.1162/002438999554101.
3. Rajeev ALUR and Pavol ČERNÝ (2010), Expressiveness of streaming string transducers, in Kamal LODAYA and Meena MAHAJAN, editors, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010), volume 8 of Leibniz International Proceedings in Informatics (LIPIcs), pp. 1–12, Schloss Dagstuhl–Leibniz-Zentrum für Informatik, Dagstuhl, Germany, http://drops.dagstuhl.de/opus/volltexte/2010/2853.
4. Bruce BAGEMIHL (1989), The crossing constraint and ‘backwards languages’, Natural Language & Linguistic Theory, 7(4):481–549.
5. Félix BASCHENIS, Olivier GAUWIN, Anca MUSCHOLL, and Gabriele PUPPIS (2017), Untwisting two-way transducers in elementary time, in 2017 32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), pp. 1–12, Reykjavik, Iceland, doi:10.1109/LICS.2017.8005138.
6. Kenneth R. BEESLEY and Lauri KARTTUNEN (2000), Finite-state non-concatenative morphotactics, in Proceedings of the 38th Annual Meeting of the Association for Computational Linguistics, pp. 191–198, Association for Computational Linguistics, Hong Kong, doi:10.3115/1075218.1075243, https://www.aclweb.org/anthology/P00-1025.
7. Karen M. BOOKER (1979), Comparative Muskogean: Aspects of Proto-Muskogean verb morphology, Ph.D. thesis, University of Kansas, Lawrence, KS.
8. Ellen I. BROSELOW (1983), Salish double reduplications: Subjacency in morphology, Natural Language & Linguistic Theory, 1:317–346.
9. Cezar CÂMPEANU, Kai SALOMAA, and Sheng YU (2002), Regex and extended regex, in Jean-Marc CHAMPARNAUD and Denis MAUREL, editors, Implementation and Application of Automata, 7th International Conference, CIAA 2002, Tours, France, July 3–5, 2002, Revised Papers, volume 2608 of Lecture Notes in Computer Science, pp. 77–84, Springer, doi:10.1007/3-540-44977-9_7, https://doi.org/10.1007/3-540-44977-9_7.
10. Cezar CÂMPEANU, Kai SALOMAA, and Sheng YU (2003), A formal study of practical regular expressions, International Journal of Foundations of Computer Science, 14(06):1007–1018.
11. Benjamin CARLE and Paliath NARENDRAN (2009), On extended regular expressions, in Language and Automata Theory and Applications: Third International Conference, LATA 2009, Tarragona, Spain, April 2-8, 2009. Proceedings 3, pp. 279–289, Springer.
12. Jane CHANDLEE (2014), Strictly local phonological processes, Ph.D. thesis, University of Delaware, Newark, DE.
13. Jane CHANDLEE (2017), Computational locality in morphological maps, Morphology, 27:599–641.
14. Jane CHANDLEE, Rémi EYRAUD, and Jeffrey HEINZ (2014), Learning strictly local subsequential functions, Transactions of the Association for Computational Linguistics, 2:491–504, doi:10.1162/tacl_a_00198, https://aclanthology.org/Q14-1038.
15. Jane CHANDLEE and Jeffrey HEINZ (2012), Bounded copying is subsequential: Implications for metathesis and reduplication, in Proceedings of the Twelfth Meeting of the Special Interest Group on Computational Morphology and Phonology, pp. 42–51, Association for Computational Linguistics, Montréal, Canada, https://www.aclweb.org/anthology/W12-2306.
16. Alexander CLARK, Makoto KANAZAWA, Gregory M KOBELE, and Ryo YOSHINAKA (2016), Distributional learning of some nonlinear tree grammars, Fundamenta Informaticae, 146(4):339–377.
17. Alexander CLARK and Ryo YOSHINAKA (2014), Distributional learning of parallel multiple context-free grammars, Machine Learning, 96(1–2):5–31, ISSN 0885-6125, doi:10.1007/s10994-013-5403-2, https://doi.org/10.1007/s10994-013-5403-2.
18. Yael COHEN-SYGAL and Shuly WINTNER (2006), Finite-state registered automata for non-concatenative morphology, Computational Linguistics, 32(1):49–82.
19. Christopher CULY (1985), The complexity of the vocabulary of Bambara, Linguistics and Philosophy, 8(3):345–351.
20. Aniello DE SANTO and Thomas GRAF (2019), Structure sensitive tier projection: Applications and formal properties, in Raffaella BERNARDI, Greg KOBELE, and Sylvain POGODALLA, editors, Formal Grammar, pp. 35–50, Springer Berlin Heidelberg, ISBN 978-3-662-59648-7.
21. Robert M. W. DIXON (1972), The Dyirbal language of North Queensland, volume 9 of Cambridge Studies in Linguistics, Cambridge University Press, Cambridge.
22. Hossep DOLATIAN and Jeffrey HEINZ (2018a), Learning reduplication with 2-way finite-state transducers, in Olgierd UNOLD, Witold DYRKA, and Wojciech WIECZOREK, editors, Proceedings of the 14th International Conference on Grammatical Inference, volume 93 of Proceedings of Machine Learning Research, pp. 67–80, PMLR.
23. Hossep DOLATIAN and Jeffrey HEINZ (2018b), Modeling reduplication with 2-way finite-state transducers, in Proceedings of the Fifteenth Workshop on Computational Research in Phonetics, Phonology, and Morphology, pp. 66–77, Association for Computational Linguistics, Brussels, Belgium, doi:10.18653/v1/W18- 5807.
24. Hossep DOLATIAN and Jeffrey HEINZ (2019), RedTyp: A database of reduplication with computational models, in Proceedings of the Society for Computation in Linguistics, volume 2, article 3.
25. Hossep DOLATIAN and Jeffrey HEINZ (2020), Computing and classifying reduplication with 2-way finite-state transducers, Journal of Language Modelling, 8(1):179–250.
26. Jason EISNER (1997), Efficient generation in primitive Optimality Theory, in
27. 35th Annual Meeting of the Association for Computational Linguistics and 8th Conference of the European Chapter of the Association for Computational Linguistics, pp. 313–320, Association for Computational Linguistics, Madrid, Spain, doi:10.3115/976909.979657, https://www.aclweb.org/anthology/P97-1040.
28. T. Mark ELLISON (1994), Phonological derivation in Optimality Theory, in Proceedings of the 15th Conference on Computational Linguistics – Volume 2, COLING 94, pp. 1007–1013, Association for Computational Linguistics, USA, doi:10.3115/991250.991312, https://doi.org/10.3115/991250.991312.
29. Joost ENGELFRIET and Hendrik Jan HOOGEBOOM (1999), MSO definable string transductions and two-way finite state transducers, doi:10.48550/ARXIV.CS/9906007, https://arxiv.org/abs/cs/9906007.
30. Dominik D. FREYDENBERGER and Markus L. SCHMID (2019), Deterministic regular expressions with back-references, Journal of Computer and System Sciences, 105:1–39.
31. Pedro GARCIA, Enrique VIDAL, and José ONCINA (1990), Learning locally testable languages in the strict sense, in Proceedings of the Workshop on Algorithmic Learning Theory, pp. 325–338.
32. Gerald GAZDAR and Geoffrey K. PULLUM (1985), Computationally relevant properties of natural languages and their grammars, New Generation Computing, 3(3):273–306.
33. David GIL (1996), How to speak backwards in tagalog, in Pan-Asiatic Linguistics, Proceedings of the Fourth International Symposium on Language and Linguistics, January 8–10, 1996, Institute of Language and Culture for Rural Development, Mahidol University at Salaya, volume 1, pp. 297–306.
34. E. Mark GOLD (1967), Language identification in the limit, Information and Control, 10(5):447–474.
35. Phyllis M. HEALEY (1960), An Agta grammar, Bureau of Printing, Manila.
36. Jeffrey HEINZ (2007), The inductive learning of phonotactic patterns, Ph.D. thesis,
37. University of California, Los Angeles.
38. Jeffrey HEINZ (2010), String extension learning, in Proceedings of the 48th Annual Meeting of the Association for Computational Linguistics, pp. 897–906, Association for Computational Linguistics, Uppsala, Sweden.
39. Jeffrey HEINZ (2018), The computational nature of phonological generalizations, in Larry HYMAN and Frans PLANK, editors, Phonological Typology, Phonetics and Phonology, chapter 5, pp. 126–195, De Gruyter Mouton.
40. 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.
41. John E HOPCROFT and Jeffrey D ULLMAN (1979), Introduction to automata theory, languages, and computation, Addison-Welsey, NY.
42. Mans HULDEN (2009), Finite-state machine construction methods and algorithms for phonology and morphology, Ph.D. thesis, University of Arizona, Tucson, USA, http://hdl.handle.net/10150/196112.
43. Riny HUYBREGTS (1984), The weak inadequacy of context-free phrase structure grammars, Van periferie naar kern, pp. 81–99.
44. Sharon INKELAS (2008), The dual theory of reduplication, Linguistics, 46(2):351–401, https://doi.org/10.1515/LING.2008.013.
45. Gerhard JÄGER and James ROGERS (2012), Formal language theory: Refining the Chomsky hierarchy, Philosophical Transactions of the Royal Society B: Biological Sciences, 367(1598):1956–1970.
46. Adam JARDINE and Jeffrey HEINZ (2016), Learning tier-based strictly 2-local languages, Transactions of the Association for Computational Linguistics, 4:87–98, ISSN 2307-387X, https: //tacl2013.cs.columbia.edu/ojs/index.php/tacl/article/view/694.
47. Aravind K. JOSHI (1985), Tree adjoining grammars: How much context-sensitivity is required to provide reasonable structural descriptions?, pp. 206–250, Studies in Natural Language Processing, Cambridge University Press, doi:10.1017/CBO9780511597855.007.
48. Laura KALLMEYER (2010), Parsing beyond context-free grammars, Cognitive Technologies, Springer, ISBN 978-3-642-14845-3, https://doi.org/10.1007/978-3-642-14846-0.
49. Ronald M. KAPLAN and Martin KAY (1994), Regular models of phonological rule systems, Computational Linguistics, 20(3):331–378.
50. Gregory M. KOBELE (2006), Generating copies: An investigation into structural identity in language and grammar, Ph.D. thesis, University of California, Los Angeles.
51. Martin KUTRIB, Andreas MALCHER, and Matthias WENDLANDT (2018), Queue automata: Foundations and developments, pp. 385–431, Springer International Publishing, Cham, ISBN 978-3-319-73216-9, https://doi.org/10.1007/978-3-319-73216-9_19.
52. Alexis MANASTER-RAMER (1986), Copying in natural languages, context-freeness, and queue grammars, in Proceedings of the 24th Annual Meeting on Association for Computational Linguistics, pp. 85–89, Association for Computational Linguistics, USA, https://doi.org/10.3115/981131.981145.
53. Alec MARANTZ (1982), Re reduplication, Linguistic Inquiry, 13(3):435–482.
54. Gary F. MARCUS, Sugumaran VIJAYAN, Shoba Bandi RAO, and Peter M. VISHTON (1999), Rule learning by seven-month-old infants, Science, 283(5398):77–80, http://www.jstor.org/stable/2897195.
55. Connor MAYER and Travis MAJOR (2018), A challenge for tier-based strict locality from Uyghur backness harmony, in Annie FORET, Greg KOBELE, and Sylvain POGODALLA, editors, Formal Grammar 2018, pp. 62–83, Springer Berlin Heidelberg, ISBN 978-3-662-57784-4.
56. Edith A. MORAVCSIK (1978), Reduplicative constructions, in Joseph GREENBERG, editor, Universals of Human Language, pp. 297–334, Stanford University Press, Stanford, CA, USA.
57. Elliott MORETON, Brandon PRICKETT, Katya PERTSOVA, Joshua FENNELL, Joe PATER, and Lisa SANDERS (2021), Learning reduplication, but not syllable reversal, in Ryan BENNETT, Richard BIBBS, Mykel Loren BRINKERHOFF, Stephanie Rich MAX J. KAPLAN, Amanda RYSLING, Nicholas Van HANDEL, and Maya Wax CAVALLARO, editors, Supplemental Proceedings of the 2020 Annual Meeting on Phonology, https://journals.linguisticsociety.org/ proceedings/index.php/amphonology/article/view/4912/4634.
58. Nicole NELSON (2005), Wrong side reduplication is epiphenomenal: Evidence from Yoruba, pp. 135–160, De Gruyter Mouton, Berlin, Boston, https://doi.org/10.1515/9783110911466.135.
59. Taishin Y. NISHIDA and Shigeko SEKI (2000), Grouped partial et0l systems and parallel multiple context-free grammars, Theoretical Computer Science, 246(1):131–150, ISSN 0304-3975, https: //www.sciencedirect.com/science/article/pii/S0304397599000766.
60. Jonathan RAWSKI, Hossep DOLATIAN, Jeffrey HEINZ, and Eric RAIMY (2023), Regular and polyregular theories of reduplication, Glossa: a Journal of General Linguistics, 8(1).
61. Jason RIGGLE (2004a), Generation, recognition, and learning in finite state
62. Optimality Theory, Ph.D. thesis, University of California, Los Angeles.
63. Jason RIGGLE (2004b), Nonlocal reduplication, in Proceedings of the 34th Meeting of the North-East Linguistics Society (NELS 34), pp. 485–496, GLSA, University of Massachusetts, USA, https://doi.org/doi:10.7282/T3GT5PZF.
64. Brian ROARK and Richard SPROAT (2007), Computational approaches to morphology and syntax, Oxford University Press, Oxford.
65. Carl RUBINO (2005), Reduplication: Form, function and distribution, pp. 11–30, De Gruyter Mouton, Berlin, Boston, https://doi.org/10.1515/9783110911466.11.
66. Carl RUBINO (2013), Reduplication, in Matthew S. DRYER and Martin HASPELMATH, editors, The World Atlas of Language Structures Online, Max Planck Institute for Evolutionary Anthropology, Leipzig, https://wals.info/chapter/27.
67. Edward SAPIR and Harry HOIJER (1967), The phonology and morphology of the Navaho language, 50, University of California Publication.
68. Walter SAVITCH (1989), A formal model for context-free languages augmented with reduplication, Computational Linguistics, 15(4):250–261, https://aclanthology.org/J89-4003.
69. Walter J. SAVITCH (1993), Why it might pay to assume that languages are infinite, Annals of Mathematics and Artificial Intelligence, 8:17–25.
70. Markus L. SCHMID (2016), Characterising REGEX languages by regular languages equipped with factor-referencing, Information and Computation, 249:1–17.
71. Hiroyuki SEKI, Takashi MATSUMURA, Mamoru FUJII, and Tadao KASAMI (1991), On multiple context-free grammars, Theoretical Computer Science, 88(2):191–229, https: //www.sciencedirect.com/science/article/pii/030439759190374B.
72. Stuart M. SHIEBER (1985), Evidence against the context-freeness of natural language, in Philosophy, Language, and Artificial Intelligence, pp. 79–89, Springer.
73. Michael SIPSER (2013), Introduction to the theory of computation, The MIT Press, Boston, MA, third edition, ISBN 113318779X.
74. Paul SMOLENSKY and Alan PRINCE (1993), Optimality Theory: Constraint interaction in generative grammar, Optimality Theory in Phonology, 3.
75. Edward P. STABLER (2004), Varieties of crossing dependencies: Structure dependence and mild context sensitivity, Cognitive Science, 93(5):699–720.
76. Jan-Olof SVANTESSON, Anna TSENDINA, Anastasia KARLSSON, and Vivan FRANZÉN (2005), The phonology of Mongolian, OUP Oxford.
77. Rachelle WAKSLER (1999), Cross-linguistic evidence for morphological representation in the mental lexicon, Brain and Language, 68(1):68–74, https: //www.sciencedirect.com/science/article/pii/S0093934X9992117X.
78. Markus WALTHER (2000), Finite-state reduplication in one-level prosodic morphology, in 1st Meeting of the North American Chapter of the Association for Computational Linguistics, https://www.aclweb.org/anthology/A00-2039.
79. Yang WANG (2021a), Recognizing reduplicated forms: Finite-State Buffered Machines, in Proceedings of the 18th SIGMORPHON Workshop on Computational Research in Phonetics, Phonology, and Morphology, pp. 177–187, Association for Computational Linguistics, Online, doi:10.18653/v1/2021.sigmorphon-1.20, https://aclanthology.org/2021.sigmorphon-1.20.
80. Yang WANG (2021b), Regular languages extended with reduplication: Formal models, proofs and illustrations, Master’s thesis, University of California, Los Angeles.
81. Samantha WRAY, Linnaea STOCKALL, and Alec MARANTZ (2022), Early form-based morphological decomposition in Tagalog: MEG evidence from reduplication, infixation, and circumfixation, Neurobiology of Language, 3(2):235–255, ISSN 2641-4368, https://doi.org/10.1162/nol_a_00062.
82. Fujimura YUKO (2001), Reduplication in standard Malay and Japanese, Journal of Modern Languages, 13(1):65–92.
83. Eva ZIMMERMANN (2019), Database of the DFG project multiple reduplication: Typology and theory, online available at http://www.evazimmermann.org/multiple-reduplication-data.html.
84. Eva ZIMMERMANN (2021a), Faded copies: Reduplication as distribution of activity, Glossa: a Journal of General Linguistics, 6(1).
85. Eva ZIMMERMANN (2021b), A phonological account of unfaithful multiple reduplication, The Linguistic Review, 38(3):537–572, https://doi.org/10.1515/tlr-2021-2075.
86. Kie ZURAW (1996), Floating phonotactics: Infixation and reduplication in Tagalog loanwords, Master’s thesis, University of California, Los Angeles.
87. Kie ZURAW (2002), Aggressive reduplication, Phonology, 19(3):395–439.

Uwagi

Opracowanie rekordu ze środków MEiN, umowa nr SONP/SP/546092/2022 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2022-2023).

Typ dokumentu

Bibliografia

Identyfikator YADDA

bwmeta1.element.baztech-677b594a-d238-4457-bfa2-25c7d71e10a4