Wyniki wyszukiwania - BazTech

Ograniczanie wyników

2 Journal of Language Modelling

2 2019

Znaleziono wyników: 2

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: finite-state

Sortuj według:

Ogranicz wyniki do:

How to embed noncrossing trees in Universal Dependencies treebanks in a low-complexity regular language

Yli-Jyrä Anssi Mikael

Journal of Language Modelling

2019

Vol. 7, No. 2

177--232

A recently proposed balanced-bracket encoding (Yli-Jyrä and Gómez-Rodríguez 2017) has given us a way to embed all noncrossing dependency graphs into the string space and to formulate their exact arcfactored inference problem (Kuhlmann and Johnsson 2015) as the best string problem in a dynamically constructed and weighted unambiguous context-free grammar. The current work improves the encoding and makes it shallower by omitting redundant brackets from it. The streamlined encoding gives rise to a bounded-depth subset approximation that is represented by a small finite-state automaton. When bounded to 7 levels of balanced brackets, the automaton has 762 states and represents a strict superset of more than 99.9999% of the noncrossing trees available in Universal Dependencies 2.4 (Nivre et al. 2019). In addition, it strictly contains all 15-vertex noncrossing digraphs. When bounded to 4 levels and 90 states, the automaton still captures 99.2% of all noncrossing trees in the reference dataset. The approach is flexible and extensible towards unrestricted graphs, and it suggests tight finite-state bounds for dependency parsing, and for the main existing parsing methods.

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

Hao Yiding

Journal of Language Modelling

2019

Vol. 7, No. 2

49--99

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.