Transition-Based Coding and Formal Language Theory for Ordered Digraphs
Transition-based parsing of natural language uses transition systems to build directed annotation graphs (digraphs) for sentences. In this paper, we define, for an arbitrary ordered digraph, a unique decomposition and a corresponding linear encoding that are associated bijectively with each other via a new transition system. These results give us an efficient and succinct representation for digraphs and sets of digraphs. Based on the system and our analysis of its syntactic properties, we give structural bounds under which the set of encoded digraphs is restricted and becomes a context-free or a regular string language. The context-free restriction is essentially a superset of the encodings used previously to characterize properties of noncrossing digraphs and to solve maximal subgraphs problems. The regular restriction with a tight bound is shown to capture the Universal Dependencies v2.4 treebanks in linguistics.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
A Unifying Theory of Transition-based and Sequence Labeling Parsing
We define a mapping from transition-based parsing algorithms that read sentences from left to right to sequence labeling encodings of syntactic trees. This not only establishes a theoretical relation between transition-b…
Dependency ParsingA tree interpretation of arc standard dependency derivation
Arc-standard derivations over projective dependency trees can be interpreted as the incremental construction of lexicalized ordered trees with contiguous yields. Each \textsc{shift}, \textsc{leftarc}, and \textsc{rightar…
On the behavior of random RNA secondary structures near the glass transition
RNA forms elaborate secondary structures through intramolecular base pairing. These structures perform critical biological functions within each cell. Due to the availability of a polynomial algorithm to calculate the pa…
Learning with Partially Ordered Representations
This paper examines the characterization and learning of grammars defined with enriched representational models. Model-theoretic approaches to formal language theory traditionally assume that each position in a string be…
PositionRelationFinancial Crisis in the Framework of Non-zero Temperature Balance Theory
Financial crises are known as crashes that result in a sudden loss of value of financial assets in large part and they continue to occur from time to time surprisingly. In order to discover features of the financial netw…
Triplet