Top

Published in:

2020 | OriginalPaper | Chapter

Input Strictly Local Tree Transducers

Authors : Jing Ji, Jeffrey Heinz

Published in: Language and Automata Theory and Applications

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

We generalize the class of input strictly local string functions (Chandlee et al. 2014) to tree functions. We show they are characterized by a subclass of frontier-to-root, deterministic, linear tree transducers. We motivate this class from the study of natural language as it provides a way to distinguish local syntactic processes from non-local ones. We give examples illustrating this kind of analysis.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter On the Weisfeiler-Leman Dimension of Fractional Packing

next chapter Lyndon Words versus Inverse Lyndon Words: Queries on Suffixes and Bordered Words

Beesley, K., Kartunnen, L.: Finite State Morphology. CSLI Publications, Stanford (2003)

Chandlee, J., Eyraud, R., Heinz, J.: Learning strictly local subsequential functions. Trans. Assoc. Comput. Linguist. 2, 491–503 (2014)CrossRef

Chandlee, J., Eyraud, R., Heinz, J.: Output strictly local functions. In: Kuhlmann, M., Kanazawa, M., Kobele, G.M. (eds.) Proceedings of the 14th Meeting on the Mathematics of Language (MoL 2015), Chicago, USA, pp. 112–125, July 2015

Chomsky, N.: The Minimalist Program. The MIT Press, Cambridge (1995)MATH

Comon, H., et al.: Tree automata techniques and applications (2007). http://tata.gforge.inria.fr/. Release 12 Oct 2007

Friese, S., Seidl, H., Maneth, S.: Minimization of deterministic bottom-up tree transducers. In: Gao, Y., Lu, H., Seki, S., Yu, S. (eds.) DLT 2010. LNCS, vol. 6224, pp. 185–196. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-14455-4_18CrossRef

Gécseg, F., Steinby, M.: Tree Automata. Akadémiai Kiadó, Budapest (2015). http://arxiv.org/abs/1509.06233. Originally published in 1984

Graf, T.: Closure properties of minimalist derivation tree languages. In: Pogodalla, S., Prost, J.-P. (eds.) LACL 2011. LNCS (LNAI), vol. 6736, pp. 96–111. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-22221-4_7CrossRef

Graf, T.: Curbing feature coding: strictly local feature assignment. In: Proceedings of the Society for Computation in Linguistics (SCiL) 2020 (2020, to appear)

10.

Graf, T., Shafiei, N.: C-command dependencies as TSL string constraints. In: Jarosz, G., Nelson, M., O’Connor, B., Pater, J. (eds.) Proceedings of SCiL 2019, pp. 205–215 (2019)

11.

Heinz, J.: The computational nature of phonological generalizations. In: Hyman, L., Plank, F. (eds.) Phonological Typology, Chap. 5, pp. 126–195. Phonetics and Phonology, De Gruyter Mouton (2018)

12.

Heinz, J., de la Higuera, C., van Zaanen, M.: Grammatical Inference for Computational Linguistics. Synthesis Lectures on Human Language Technologies, Morgan and Claypool (2015)CrossRef

13.

Knight, K., May, J.: Applications of weighted automata in natural language processing. In: Droste, M., Kuich, W., Vogler, H. (eds.) Handbook of Weighted Automata, Chap. 14. EATCS, pp. 571–596. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-01492-5_14

14.

Kobele, G.M.: Minimalist tree languages are closed under intersection with recognizable tree languages. In: Pogodalla, S., Prost, J.-P. (eds.) LACL 2011. LNCS (LNAI), vol. 6736, pp. 129–144. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-22221-4_9CrossRef

15.

Maletti, A.: Survey: tree transducers in machine translation. In: Bordihn, H., Freund, R., Hinze, T., Holzer, M., Kutrib, M., Otto, F. (eds.) Proceedings of the 2nd International Workshop on Non-Classical Models of Automata and Applications. books@ocg.at, vol. 263, pp. 11–32. Österreichische Computer Gesellschaft (2010)

16.

McNaughton, R., Papert, S.: Counter-Free Automata. MIT Press, Cambridge (1971)MATH

17.

Roark, B., Sproat, R.: Computational Approaches to Morphology and Syntax. Oxford University Press, Oxford (2007)

18.

Rogers, J.: Strict LT\(_2\): regular \({:}{:}\) local : recognizable. In: Retoré, C. (ed.) LACL 1996. LNCS, vol. 1328, pp. 366–385. Springer, Heidelberg (1997). https://doi.org/10.1007/BFb0052167CrossRef

19.

Rogers, J.: A Descriptive Approach to Language-Theoretic Complexity. CSLI Publications, Stanford (1998)MATH

20.

Rogers, J., Pullum, G.: Aural pattern recognition experiments and the subregular hierarchy. J. Log. Lang. Inf. 20, 329–342 (2011)MathSciNetCrossRef

21.

Sportiche, D., Koopman, H., Stabler, E.: An Introduction to Syntactic Analysis and Theory. Wiley, Hoboken (2013)

Title: Input Strictly Local Tree Transducers
Authors: Jing Ji
Jeffrey Heinz
Publisher: Springer International Publishing
Book: Language and Automata Theory and Applications
Print ISBN: 978-3-030-40607-3

Electronic ISBN: 978-3-030-40608-0

Copyright Year: 2020
DOI: https://doi.org/10.1007/978-3-030-40608-0_26

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner