检索结果-内蒙古大学图书馆

IWPT 2011

作者： Meixun Jin Hwidong Na Jong-Hyeok Lee Pohang University of Science and Technology (POSTECH) Hyoja Dong Pohang Republic of Korea

ISBN: (纸本)9781932432046

In this paper, we give a summary of various dependency chart parsing algorithms in terms of the use of parsing histories for a new dependency arc decision. Some parsing histories are closely related to the target dependency arc, and it is necessary for the parsing algorithm to take them into consideration. Each dependency treebank may have some unique characteristics, and it requires for the parser to model them by certain parsing histories. We show in experiments that proper selection of the parsing algorithm which reflect the dependency annotation of the coordinate structures improves the overall performance.

关键词： parsing algorithms parsing Parser DEPENDENCE

来源：评论

学校读者我要写书评

暂无评论

Improved algorithms for parsing ESLTAGs: A Grammatical Model Suitable for RNA Pseudoknots

引用

IEEE-ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS 2010年第4期7卷 619-627页

作者： Rajasekaran, Sanguthevar Al Seesi, Sahar Ammar, Reda A. Univ Connecticut Dept Comp Sci & Engn Storrs CT 06269 USA

Formal grammars have been employed in biology to solve various important problems. In particular, grammars have been used to model and predict RNA structures. Two such grammars are Simple Linear Tree Adjoining Grammars (SLTAGs) and Extended SLTAGs (ESLTAGs). Performances of techniques that employ grammatical formalisms critically depend on the efficiency of the underlying parsing algorithms. In this paper, we present efficient algorithms for parsing SLTAGs and ESLTAGs. Our algorithm for SLTAGs parsing takes O(min{m, n(4)}) time and O(min{m, n(4)}) space, where m is the number of entries that will ever be made in the matrix M (that is normally used by TAG parsing algorithms). Our algorithm for ESLTAGs parsing takes O(nmin{m, n(4)}) time and O(min{m, n(4)}) space. We show that these algorithms perform better, in practice, than the algorithms of Uemura et al. [21].

关键词： RNA structure analysis tree adjoining grammars parsing algorithms

来源：评论

学校读者我要写书评

暂无评论

Probabilistic parsing strategies

引用

JOURNAL OF THE ACM 2006年第3期53卷 406-436页

作者： Nederhof, Mark-Jan Satta, Giorgio Univ Groningen Fac Arts NL-9700 AS Groningen Netherlands Univ Padua Dept Informat Engn I-35131 Padua Italy

We present new results on the relation between purely symbolic context-free parsing strategies and their probabilistic counterparts. Such parsing strategies are seen as constructions of push-down devices from grammars. We show that preservation of probability distribution is possible under two conditions, viz. the correct-prefix property and the property of strong predictiveness. These results generalize existing results in the literature that were obtained by considering parsing strategies in isolation. From our general results, we also derive negative results on so-called generalized LR parsing.

关键词： algorithms theory parsing algorithms probabilistic parsing transduction context-free grammars push-down automata

来源：评论

学校读者我要写书评

暂无评论

Practical Earley parsing

引用

COMPUTER JOURNAL 2002年第6期45卷 620-630页

作者： Aycock, J Horspool, RN Univ Calgary Dept Comp Sci Calgary AB T2N 1N4 Canada Univ Victoria Dept Comp Sci Victoria BC V8W 3P6 Canada

Earley's parsing algorithm is a general algorithm, able to handle any context-free grammar. As with most parsing algorithms, however, the presence of grammar rules having empty right-hand sides complicates matters. By analyzing why Earley's algorithm struggles with these grammar rules, we have devised a simple solution to the problem. Our empty-rule solution leads to a new type of finite automaton expressly suited for use in Earley parsers and to a new statement of Earley's algorithm. We show that this new form of Earley parser is much more time efficient in practice than the original.

关键词： context-free grammars algorithms parsing finite state machines Parser syntax PROBLEM SOLUTION parsing algorithms

来源：评论

学校读者我要写书评

暂无评论

Weighted deductive parsing and Knuth's algorithm - Squibs and discussions

引用

COMPUTATIONAL LINGUISTICS 2003年第1期29卷 135-143页

作者： Nederhof, MJ Univ Groningen Fac Arts Humanities Comp NL-9700 AS Groningen Netherlands German Res Ctr Artificial Intelligence Saarbrucken Germany

We discuss weighted deductive parsing and consider the problem of finding the derivation with the lowest weight. We show that Knuth's generalization of Dijkstra's algorithm for the shortest-path problem offers a general method to solve this problem. Our approach is modular in the sense that Knuth's algorithm is formulated independently from the weighted deduction system.

关键词： .parser derivation parsing algorithms Weighted Deductive parsing Knuth Algorithm generalization of Dijkstra weighted deduction

来源：评论

学校读者我要写书评

暂无评论

Watson-Crick Context-Free Grammars: Grammar Simplifications and a parsing Algorithm

引用

COMPUTER JOURNAL 2018年第9期61卷 1361-1373页

作者： Zulkufli, Nurul Liyana Mohamad Turaev, Sherzod Tamrin, Mohd Izzuddin Mohd Messikh, Azeddine Int Islamic Univ Malaysia Dept Comp Sci Kulliyyah Informat & Commun Technol Kuala Lumpur Malaysia

A Watson-Crick (WK) context-free grammar, a context-free grammar with productions whose right-hand sides contain nonterminals and double-stranded terminal strings, generates complete double-stranded strings under Watson-Crick complementarity. In this paper, we investigate the simplification processes of Watson-Crick context-free grammars, which lead to defining Chomskylike normal form for Watson-Crick context-free grammars. The main result of the paper is a modified CYK (Cocke-Younger-Kasami) algorithm for Watson-Crick context-free grammars in WK-Chomsky normal form, allowing to parse double-stranded strings in O (n(6)) time.

关键词： DNA Computing formal languages parsing algorithms Watson-Crick grammars Watson-Crick automata grammar simplifications context-free grammars

来源：评论

学校读者我要写书评

暂无评论

On optimal parsing for LZ78-like compressors

引用

THEORETICAL COMPUTER SCIENCE 2018年 710卷 19-28页

作者： Aronica, Salvatore Langiu, Alessio Marzi, Francesca Mazzola, Salvatore Mignosi, Filippo CNR IAMC Natl Res Council Unit Capo Granitola Trapani Italy CNR ICAR Natl Res Council Unit Palermo Palermo Italy Kings Coll London Dept Informat London England Univ LAquila DISIM Dept Laquila Italy

Flexible parsing algorithm, a two-steps-greedy parsing algorithm for text factorisation, has been proved to be an optimal parsing for LZ78-like compressors in the case of constant cost phrases [1,2]. Whilst in early implementations of LZ78-like compressors the phrases have constant cost, in common modern implementations the cost of the k-th phrase is [log(2) k + C] where C is a real constant [3,4]. Indeed we show examples where Flexible parsing is not optimal under the above more realistic setting. In this paper we prove that, under the assumption that the cost of a phrase is block-wise constant and non-decreasing, the Flexible parsing is almost optimal. For almost optimal we mean that, for any text T, the difference between the sizes of the compressed text obtained by using a Flexible parsing and an optimal parsing is bounded by the maximal cost of a phrase in T, i.e. it is logarithmic in practical cases. Furthermore we investigate how an optimal parsing, and hence an almost optimal parsing, affects the rate of convergence to the entropy of LZ78-like compressors. We discuss some experimental results considering the ratio between the speed of convergence to the entropy of compressors with and without an optimal parsing. This ratio presents a kind of wave effect that increases as the entropy of a memoryless source decreases but it seems always to slowly converge to one. According to the theory, this wave can be a tsunami for some families of highly compressible strings and, although the optimal (and the almost optimal) parsing does not improve the asymptotical speed of convergence to the entropy, it can improve compression ratio, and hence the decoding speed, in many practical cases. (C) 2017 Elsevier B.V. All rights reserved.

关键词： Lempel-Ziv compression algorithms parsing algorithms Text factorisation Text compression Text entropy String algorithms

来源：评论

学校读者我要写书评

暂无评论

A polynomial-time parsing algorithm for K-depth languages

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 1996年第1期52卷 61-79页

作者： Cherubini, A SanPietro, P POLITECN MILAN DIPARTIMENTO ELETTRON & INFORMAZI-20133 MILANITALY JAPAN ADV INST SCI & TECHNOL SCH INFORMAT SCITATSUNOKUCHI 92312JAPAN

K-depth grammars extend context-free grammars allowing k greater than or equal to 1 rewriting points for a single non-terminal at every step of a derivation. The family of languages generated by k-depth grammars is a proper extension of the family of context-free languages, while retaining many context-free properties, such as closure properties, a version of Chomsky-Schutzenberger theorem, the existence of an accepting device (the multi-pushdown automaton). Here a polynomial-time parsing algorithm for k-depth languages is defined, and its correctness is proved. (C) 1996 Academic Press, Inc.

关键词： closure property accuracy class context-free grammars Greater than or equal to pushdown automata Language Automata parsing algorithms syntax context-free context-free languages Robot family

来源：评论

学校读者我要写书评

暂无评论

INCREMENTAL SCANNING AND parsing WITH GALAXY

引用

IEEE TRANSACTIONS ON SOFTWARE ENGINEERING 1991年第7期17卷 641-651页

作者： BEETEM, JF BEETEM, AF AB CREAT CONSULTING INC MADISONWI 53705

Incremental integrated programming environments are a promising approach toward the goal of improved programmer productivity. Consistently rapid environment response is an obvious goal. Efficient use of storage has also been determined to be an important issue. This paper presents the algorithms and techniques used for incremental scanning and parsing of the Galaxy language. The algorithms guarantee minimal rescanning and reparsing and are also space and time efficient. Notably, the methods are easily adapted to any language of equivalent class, i.e., RL(1) intersects LR(1), including such languages as C and Pascal.

关键词： EXTENSIBLE LANGUAGES INCREMENTAL COMPILATION INCREMENTAL parsing INCREMENTAL SCANNING INTEGRATED SOFTWARE TOOLS LANGUAGE-BASED EDITORS (LBES) parsing algorithms PROGRAMMER PRODUCTIVITY SOFTWARE ENGINEERING ENVIRONMENTS

来源：评论

学校读者我要写书评

暂无评论

Program extraction applied to monadic parsing

引用

JOURNAL OF LOGIC AND COMPUTATION 2019年第4期29卷 487-518页

作者： Berger, Ulrich Jones, Alison Seisenberger, Monika Swansea Univ Comp Sci Swansea SA2 8PP W Glam Wales

This article outlines a proof-theoretic approach to developing correct and terminating monadic parsers. Using modified realizability, we extract formally verified and terminating programs from formal proofs. By extracting both primitive parsers and parser combinators, it is ensured that all complex parsers built from these are also correct, complete and terminating for any input. We demonstrate the viability of our approach by means of two case studies: we extract (i) a small arithmetic calculator and (ii) a non-deterministic natural language parser. The work is being carried out in the interactive proof system Minlog.

关键词： Program extraction verification monads parsing algorithms natural language processing termination left recursion

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：