TAILIEUCHUNG - Báo cáo khoa học: "Computer and Information Science"

We will describe an Earley-type parser for Tree Adjoining Grammars (TAGs). Although a CKYtype parser for TAGs has been developed earlier (Vijay-Shanker and :Icshi, 1985), this is the first practical parser for TAGs because as is well known for CFGs, the average behavior of Earley-type parsers is superior to that of CKY-type parsers. The core of the algorithm is described. Then we discuss modifications of the parsing algorithm that can parse extensions of TAGs such as constraints on adjunction, substitution, and feature structures for TAGs. We show how with the use of substitution in TAGs the system is able. | AN EARLEY-TYPE PARSING ALGORITHM FOR TREE ADJOINING GRAMMARS Yves Schabes and Aravind K. Joshi Department of Computer and Information Science University of Pennsylvania Philadelphia PA 19104-6389 USA schabes@ joshi@ ABSTRACT We will describe an Earley-type parser for Tree Adjoining Grammars TAGs . Although a CKY-type parser for TAGs has been developed earlier Vijay-Shanker and Joshi 1985 this is the first practical parser for TAGs because as is well known for CFGs the average behavior of Earley-type parsers is superior to that of CKY-type parsers. The core of the algorithm is described. Then we discuss modifications of the parsing algorithm that can parse extensions of TAGs such as constraints on adjunction substitution and feature structures for TAGs. We show how with the use of substitution in TAGs the system is able to parse directly CFGs and TAGs. The system parses unification formalisms that have a CFG skeleton and also those with a TAG skeleton. Thus it also allows us to embed the essential aspects of PATR-II. 1 Introduction Although formal properties of Tree Adjoining Grammars TAGs have been investigated Vijay-Shanker 1987 for example there is an O n6 -time CKY-like algorithm for TAGs Vijay-Shanker and Joshi 1985 so far there has been no attempt to develop an Earley-type parser for TAGs. This paper presents an Earley parser for TAGs and discusses modifications to the parsing algorithm that make it possible to handle extensions of TAGs such as constraints on adjunction sub This work is partially supported by ARO grant DAA29-84-9-007 DARPA grant N0014-85-K0018 NSF grants MCS-82-191169 and DCR-84-10413. The authors would like to express their gratitude to Vijay-Shanker for his helpful comments relating to the core of the algorithm Richard Billington and Andrew Chainick for their graphical TAG editor which we integrated in our system and for their programming advice. Thanks are also due to Anne Abeillé and Ellen Hays. stitution and

• Báo cáo khoa học
• Computer and Information Science
• Yves Schabes
• Aravind K
• Joshi
• scientific reports
• model language
• process natural language
• Global journal of computer science
• Global journal of computer science and technology
• Information & technology
• GIS based fire emergency response system
• Computer Literacy
• Lecture Computer literacy
• Computer science
• Introduction to computers
• Computer applications
• Computer Networks
• Information society
• transaction processing
• database
• information management
• computer tricks
• computer skills
• informatics reference materials
• computer software
• computer science advanced
• teaching computer science
• programming C
• English majors
• English computer science
• English materials sector informatics
• Theoretical computer science
• Information technology study
• Information technology language
• Computer systems
• Building information systems
• Information systems
• Management information system
• International Journal of Computer Science & Communication Networks
• Study of information hiding techniques
• Information hiding techniques like steganography
• Down through age
• Information hiding classification
• Transaction processing systems
• Computer Vision
• Imagine processing
• Beyond bags of features
• Adding spatial information
• Spatial pyramid representation
• Master thesis in computer science
• Operational detection
• Information technology
• Management method
• Developing satellite based ships detection
• Information and communication technology
• Scientometric analysis of the emerging topics
• General computer science
• Peer review process
• Metrics provide guidelines
• Journal of Computer Science and Cybernetics
• Symbolic computational models for intuitionistic linguistic information
• Intuitionistic linguistic information
• Linguistic symbolic computational model
• Intuitionistic linguistic label
• Group decision making
• Linguistic preference relation
• International Journal of Computer Science and Communication Networks
• Intelligent public transport system
• Information forensics and security
• Wi Fi or GPRS technology
• Intelligent Public Transport Information System
• Issues in data mining and information retrieval
• Information retrieval and data warehousing
• The nature of the available data
• Techniques and programs used in bidding
• Playing phases of imperfect information game – an overview
• Imperfect information game
• Bridge bidding and playing phases
• Automated personal email organizer
• Information management and text mining application
• Timely response of emails
• Incoming email messages
• Automated event information extraction
• Fault tolerance approach in mobile agents
• Information retrieval applications using check points
• Information retrieval applications
• Mobile agents in Internet application
• Reliable migration time
• Examining a pipelined approach
• Information extraction with respect to machine learning
• Information extraction with respect
• Journal of Computer science
• Storing hypergraph based data models
• Non hypergraph data storage
• Applications for information systems
• Graph representation
• Introduction to TCP IP Networks
• Other Types of Hardware
• Computer tips
• Information processing cycle
• Computer hardware
• Software runs the machine
• technology information
• computer graphics
• Media Arts
• graphic designers
• digital media