Notes:
The Cocke–Younger–Kasami (CYK) algorithm is a parsing algorithm used to determine whether a given string of symbols can be generated by a given context-free grammar. It is an efficient, bottom-up algorithm that works by constructing a parse tree for a given string of symbols, starting with the individual symbols and working up to the root of the tree. The algorithm is named after its inventors, John Cocke, Daniel Younger, and Tadao Kasami, who published it in 1961.
The CYK algorithm is widely used in natural language processing and computational linguistics for tasks such as syntax analysis and parsing, and it has been applied to a variety of other domains as well. It is also known for its high time complexity, which makes it less suitable for use in some applications.
A CYK parser is a type of computer program that uses the Cocke-Younger-Kasami (CYK) algorithm to parse a string of symbols according to a given context-free grammar. The parser typically consists of three main components:
- A lexer: This component is responsible for breaking the input string down into a sequence of individual tokens, or lexemes, which can be recognized by the parser.
- A grammar: This component specifies the rules for constructing valid strings of symbols according to the context-free grammar. It typically consists of a set of productions, or rewrite rules, that define how nonterminal symbols can be replaced by sequences of other symbols.
- A parser: This component uses the CYK algorithm to construct a parse tree for the input string, starting with the individual tokens and working up to the root of the tree. The parse tree represents the structure of the input string according to the grammar, and it can be used to extract information about the meaning of the input or to generate output in a different format.
In operation, a CYK parser typically processes the input string by first breaking it down into individual tokens, and then using the CYK algorithm to construct a parse tree for the input. The parser begins by creating a table of cells, with each cell representing a subrange of the input string. It then fills in the cells of the table by considering the tokens in each subrange and the rules of the grammar, until the entire input string has been processed and a parse tree has been constructed. The parse tree can then be used to extract information about the input or to generate output in a different format.
The CYK algorithm is a parsing algorithm that is typically used to parse strings of symbols according to a given context-free grammar. While the algorithm itself is not specifically related to natural language, it is often used in natural language processing (NLP) systems to parse natural language inputs.
In NLP, context-free grammars are used to specify the structure of valid sentences in a particular natural language. A context-free grammar consists of a set of rewrite rules, or productions, that define how nonterminal symbols can be replaced by sequences of other symbols, including terminal symbols such as words and punctuation marks.
The CYK algorithm can be used to parse a sentence in a natural language by treating the words in the sentence as terminal symbols and the structure of the sentence as a sequence of nonterminal symbols. The algorithm processes the input sentence by constructing a parse tree that represents the structure of the sentence according to the grammar, and it can be used to extract information about the meaning of the sentence or to generate output in a different format.
For example, a CYK parser might be used in an NLP system to parse a sentence in English and extract information about the noun phrases and verb phrases in the sentence, or to generate a translation of the sentence into another language. So, in this way, natural language is related to CYK.
Wikipedia:
See also:
A new hybrid dependency parser for German R Sennrich, G Schneider, M Volk… – Proceedings of the German …, 2009 – files.ifi.uzh.ch … 3 CYK Parser Chunker, Tagger, Head- Extractor Raw Text … In Nicolov, N., Boncheva, K., Angelova, G., Mitkov, R., eds.: Recent Advances in Natural Language Processing IV: Selected Papers from RANLP 2005, Amsterdam, John Benjamins (2006) 2. Rehbein, I., van Genabith, J … Cited by 30 Related articles All 2 versions Cite Save More
Linear complexity context-free parsing pipelines via chart constraints B Roark, K Hollingshead – … of Human Language Technologies: The 2009 …, 2009 – dl.acm.org … of accuracy? In this paper, we adopt the same paradigm pur- sued in Roark and Hollingshead (2008), but apply it to an exact inference CYK parser (Cocke and Schwartz, 1970; Younger, 1967; Kasami, 1965). We demonstrate … Cited by 21 Related articles All 9 versions Cite Save
Data-driven parsing with probabilistic linear context-free rewriting systems L Kallmeyer, W Maier – Proceedings of the 23rd International Conference …, 2010 – dl.acm.org … Abstract This paper presents a first efficient imple- mentation of a weighted deductive CYK parser for Probabilistic Linear Context- Free Rewriting Systems (PLCFRS), to- gether with context-summary estimates for parse items used to speed up pars- ing. … 3 The CYK Parser … Cited by 19 Related articles All 9 versions Cite Save
Direct parsing of discontinuous constituents in German W Maier – Proceedings of the NAACL HLT 2010 First Workshop …, 2010 – dl.acm.org … Goal: [S, ??0,n??] Figure 3: Weighted CYK deduction system 2.2 A CYK Parser for PLCFRS We use the parser of Kallmeyer and Maier (2010). It is a probabilistic CYK parser (Seki et al., 1991), using the technique of weighted deductive parsing (Nederhof, 2003). … Cited by 20 Related articles All 12 versions Cite Save
Using web-scale N-grams to improve base NP parsing performance E Pitler, S Bergsma, D Lin, K Church – Proceedings of the 23rd …, 2010 – dl.acm.org … improves substantially over the base- line of assuming a completely right-branching structure, 95.4% versus 72.6% (Table 2). The ac- curacy of the constituency classifier itself (before the CYK parser is used … Scaling to very very large corpora for natural language disambiguation. … Cited by 14 Related articles All 15 versions Cite Save
A language specification tool for model-based parsing L Quesada, F Berzal, JC Cubero – Intelligent Data Engineering and …, 2011 – Springer … Natural language processing [9] in restricted lexical and syntactic domains. – The corpus-based induction of models [12]. … Existing parsers for unrestricted context-free grammar parsing, as the CYK parser [24,10] and the Earley parser [5], can consider syntactic ambiguities. … Cited by 8 Related articles All 5 versions Cite Save
Discontinuity and non-projectivity: Using mildly context-sensitive formalisms for data-driven parsing W Maier, L Kallmeyer – Proceedings of TAG, 2010 – research.att.com … 2.2 PLCFRS Parsing Our parser is a probabilistic CYK parser (Seki et al., 1991), using the technique of weighted deduc- tive parsing (Nederhof, 2003). … Michael Collins. 1999. Head-driven statistical models for natural language parsing. Ph.D. thesis, University of Pennsylvania. … Cited by 11 Related articles All 4 versions Cite Save More
Unsupervised concept-to-text generation with hypergraphs I Konstas, M Lapata – Proceedings of the 2012 Conference of the North …, 2012 – dl.acm.org … has focused on generating natural language sentences from logical form (ie, lambda- expressions) using mostly synchronous context-free grammars (SCFGs … Secondly, they are more efficient and faster than the common CYK parser-based representation for PCFGs by a factor of … Cited by 9 Related articles All 8 versions Cite Save
PLCFRS parsing of English discontinuous constituents K Evang, L Kallmeyer – … of the 12th International Conference on Parsing …, 2011 – dl.acm.org … 2.2 CYK Parsing We use the parser from Kallmeyer and Maier (2010); Maier (2010), Maier and Kallmeyer (2010) which is a probabilistic version of the CYK parser from Seki et al. (1991), applying techniques of weighted deductive parsing (Nederhof, 2003). … Cited by 6 Related articles All 11 versions Cite Save
A compiler for parsing schemata C Gómez?Rodríguez, J Vilares… – Software: Practice and …, 2009 – Wiley Online Library … This compiler has proven very useful for analyzing, prototyping and comparing natural-language parsers in real domains, as can be seen in the empirical examples provided at the end of the paper. Copyright © 2008 John Wiley & Sons, Ltd. … Cited by 6 Related articles All 8 versions Cite Save
Simple, functional, sound and complete parsing for all context-free grammars T Ridge – Certified Programs and Proofs, 2011 – Springer … query languages), programming languages (syntax), network proto- cols (packet formats), the internet (transfer protocols and markup languages), and natural language processing. … For comparison, the time complexity of Earley parsers, CYK parsers, and GLR parsers is O(n3 ). … Cited by 7 Related articles All 9 versions Cite Save
Deriving a probabilistic syntacto-semantic grammar for biomedicine based on domain-specific terminologies JW Fan, C Friedman – Journal of biomedical informatics, 2011 – Elsevier … Abstract. Biomedical natural language processing (BioNLP) is a useful technique that unlocks valuable information stored in textual data for practice and/or research. Syntactic … parsers. 2. Background. 2.1. Natural language parsing. … Cited by 5 Related articles All 14 versions Cite Save
Data-driven parsing using probabilistic linear context-free rewriting systems L Kallmeyer, W Maier – Computational Linguistics, 2013 – MIT Press … This paper presents the first efficient implementation of a weighted deductive CYK parser for Probabilistic Linear Context-Free Rewriting Systems (PLCFRSs). … We have implemented a CYK parser and we present several methods for context summary estimation of parse items. … Cited by 7 Related articles All 7 versions Cite Save
Lattice parsing to integrate speech recognition and rule-based machine translation S Köprü, A Yazici – Proceedings of the 12th Conference of the European …, 2009 – dl.acm.org … hypothesis. Chow and Roukos (1989) used a unification-based CYK parser for the purpose of speech understanding. Chien et al. … parses. Ney (1991) deals with the use of probabilis- tic CYK parser for continous speech recognition task. … Cited by 3 Related articles All 8 versions Cite Save
Gramin: a system for incremental learning of programming language grammars D Saha, V Narula – Proceedings of the 4th India Software Engineering …, 2011 – dl.acm.org … grammar in programming language domains and other do- mains are the bigger size of the samples, and the complexities of the programming language grammar eg presence of recursion, nest- ing, scoping which do not exist typically in natural language gram- mar … CYK Parser. … Cited by 2 Related articles All 2 versions Cite Save
Structured language models for statistical machine translation Y Zhang – 2009 – lti.cs.cmu.edu … Struc- tured language model tries to model the structural information in natural language, especially the long-distance dependencies in a probabilistic framework. … 92 6-19 Dependency tree by CYK parser with d2-gram model from unsupervised training. 3 … Cited by 9 Related articles All 4 versions Cite Save More
Fuzzy Grammar-based Prediction of Amyloidogenic Regions. O Unold – Journal of Machine Learning Research-Proceedings …, 2012 – jmlr.org … The environment of CFG is substituted by an array of CYK parser (note that the clas- sifier system can be regarded as an … Note that many problems both in natural language processing and bioinformatics can be described by a fuzzy grammar due to imprecision and fuzziness. … Cited by 1 Related articles All 3 versions Cite Save More
Word buffering models for improved speech repair parsing T Miller – … Conference on Empirical Methods in Natural Language …, 2009 – dl.acm.org Proceedings of the 2009 Conference on Empirical Methods in Natural Language Processing, pages 737–745, Singapore, 6-7 August … into a fixed-depth Hierarchical Hidden Markov Model to achieve improved parsing and reparandum-finding results over standard CYK parsers. … Cited by 2 Related articles All 12 versions Cite Save
A large neighbourhood search approach to the multi-activity shift scheduling problem CG Quimper, LM Rousseau – Journal of Heuristics, 2010 – Springer … S ? AB, A ? AA | a, B ? BB | b The CYK parser (Cocke and Schwartz 1970; Kasami 1965; Younger 1967) is an algorithm based on dynamic programming that decides whether a sequence belongs to a context-free language. … Cited by 25 Related articles All 9 versions Cite Save
[BOOK] Parsing beyond context-free grammars L Kallmeyer – 2010 – Springer … For some natural language phenomena, TAGs are too limited to provide a linguistically adequate analysis, for instance for certain extraction phenom- ena and word order variations in so-called free word order languages (Kroch and Joshi, 1987; Becker, Joshi, and Rambow … Cited by 47 Related articles All 9 versions Cite Save
Error Recovery in a Natural-Language Parser FJ de Wilde – dickgrune.com … The given affix-grammar is processed and rewritten to an equivalent Context-Free Grammar(CFG), which then is transformed to a CFG in Chomsky Normal-Form(CNF), being the suitable form we need in the core of the natural-language parser, which is formed by a CYK-parser. … Related articles All 8 versions Cite Save More
Natural Language in Blocks Worlds NC Petersen – 2010 – etd.dtu.dk Page 1. Natural Language in Blocks Worlds Niklas Christoffer Petersen … IMM-BSc: ISSN 0909-3192 Page 3. Summary This project concerns natural language processing in strictly limited domains, and the potential of natural language as user interfaces to such domains. … Related articles All 5 versions Cite Save
Mathematics, Computing, Language, and Life: Frontiers in Mathematical Linguistics and Language Theory: Volume C Gómez – World Scientific … 60 4. Practical complexity of constituency parsers 63 4.1 Parsing natural language with CFGs . . . . . … 58 4.1 Schema file for the CYK parser used in the experiments. . . . . 66 4.2 Schema file for the Left-Corner parser used in the experiments. 67 … All 3 versions Cite Save
Parsing: Process Of Analyzing With The Rules Of A Formal Grammar N CHHILLAR, N YADAV, N JAISWAL – indusedu.org … to be effective. Parsing algorithms used for natural language cannot rely on the grammar having ‘good’ properties as with manually designed grammars for programming languages. … o Canonical LR (LR(1)) parser o GLR parser • CYK parser • Recursive ascent parser … Cite Save More
Weighted Deductive Parsing using Probabilistic Linear Context-Free Rewriting Systems L Kallmeyer, W Maier – … WATA 2012 Dresden, Germany, May 29- … – wwwtcs.inf.tu-dresden.de … here presents the first efficient implementation of a weighted deduc- tive CYK parser for Probabilistic Linear Context-Free Rewriting Systems (PLCFRS). The parser is evaluated on the German treebank NeGra. In the context of data-driven natural language parsing, challenges … Cite Save More
Fence-An Efficient Parser with Ambiguity Support for Model-Driven Language Specification L Quesada, F Berzal, FJ Cortijo – arXiv preprint arXiv:1107.4687, 2011 – arxiv.org … Natural language processing [8] in restricted lexical and syntactic domains. • Corpus-based induction of models [11]. … Existing parsers for unrestricted context-free grammar parsing, as the CYK parser [9, 22] and the Earley parser [5], can consider syntactic ambiguities. … Related articles All 4 versions Cite Save
Syntactic Approaches for Natural Language Processing JA Sánchez – videolectures.net Page 1. Syntactic Approaches for Natural Language Processing Joan Andreu Sánchez Departamento Sistemas Informáticos y Computación … Introduction to the problem 6 Page 10. 1.1 Introduction Knowledge levels in Natural Language: Morphology: word structure Syntax: … Related articles Cite Save More
Introduction to Stochastic Context Free Grammars R Giegerich – techfak.uni-bielefeld.de … 2 Amusingly, the natural language processing community consistently refers to it as the CKY algorithm … In general, a CYK parser has a parser parseX for each X ?V, and the parser has as many cases to distinguish as there are alternative rules for X. The axiom parser called with … Related articles All 3 versions Cite Save More
Linear Context-Free Rewriting Systems L Kallmeyer – Language and Linguistics Compass, 2013 – Wiley Online Library … 1987). Joshi’s hypothesis that natural languages are mildly context-sensitive has been questioned by two natural language phenomena that seem to display non … In the following, we present the non-directional bottom-up parsing algorithm (CYK parser) for LCFRS from (Seki et al … Related articles All 3 versions Cite Save
Amharic Sentence Parsing Using Base Phrase Chunking A Ibrahim, Y Assabie – Computational Linguistics and Intelligent Text …, 2014 – Springer … Parsing plays a significant role in many natural language processing (NLP) applications as their efficiency relies on having an effective parser. … Among the widely known top-down and bottom-up parsers are Early parser and CYK parser, respectively [5], [8]. Since automatic … Cite Save
Tree Wrapping for Role and Reference Grammar L Kallmeyer, R Osswald, RD Van Valin Jr – Formal Grammar, 2013 – Springer … a CYK parser for grammars of this type. 1 Introduction The approach to tree construction and parsing presented in this paper is part of a larger project that aims at a full formalization of Role and Reference Grammar (RRG). RRG is a theory of the grammar of natural language … Related articles All 2 versions Cite Save
Einführung in die Computerlinguistik Probabilistic CFG L Kallmeyer – user.phil-fak.uni-duesseldorf.de … Page 5. Kallmeyer CL-Einführung Parsing (2) We can extend the symbolic CYK parser to a probabilistic one. … Speech and Language Processing. An Introduction to Natural Language Processing, Computational Linguistics, and Speech Recognition. … Related articles Cite Save More
Parsing: Preliminaries PDDL Kallmeyer – Parsing Beyond Context-Free Grammars, 2010 – Springer … Deterministic parsing approaches such as LL(k) parsing (Sippu and Soisalon-Soininen, 1990) are therefore not adequate. There are two aspects arising from the ambiguity of natural language syn- tax: … In the context of CFGs, the CYK parser and the Earley parser (see Fig. … Related articles All 2 versions Cite Save
A Framework for Unsupervised Dependency Parsing Using a soft-EM Algorithm and Bilexical Grammars MA Dom?nguez, G Infante-Lopez – pics.cicling.org … Unsupervised dependency parsing is acquiring great relevance in the area of Natural Language Processing due to the increasing number of utterances … Our model is implemented by means of a k-best CYK parser, an inductor for Probabilistic Bilexical Grammars (PBGs) [8] and … Related articles All 3 versions Cite Save More
A Constraint-Satisfaction Parser for Context-Free Grammars L Quesada, F Berzal, FJ Cortijo – arXiv preprint arXiv:1110.1470, 2011 – arxiv.org … The Universal parser [23] is a GLR parser used for natural language processing. However, it fails for grammars with epsilon productions and infinitely recursive production sets. Existing chart parsers for unrestricted context-free grammar parsing, as the CYK parser [12, 25] and … Related articles All 4 versions Cite Save
List of Acronyms BOSBO Sentence, CFGCF Grammar, CNFCN Form… – World Scientific … parsing of syntactic and semantic depen- dencies, in Proceedings of the 12th Conference on Computational Natural Language Learning (CoNLL … Covington’s projective parser, 180 custom elements, see extensibility cycle detection, 193 cycle elimination, 190 CYK parser, 18–23 … Related articles Cite Save
Fencing the Lamb: A Chart Parser for ModelCC L Quesada, F Berzal, FJ Cortijo – Software and Data Technologies, 2013 – Springer … The Universal parser [28] is a GLR parser used for natural language processing. However, it fails for grammars with epsilon productions and infinitely recursive production sets. Existing chart parsers for unrestricted context-free grammar parsing, as the CYK parser [30,12] and … Related articles All 2 versions Cite Save
Web Based Application for Hindi Question Answering System S Stalin, R Pandey, R Barskar – ijecse.org … The implementation is done in java and it also integrates CYK parser, NLP building modules, Query formulation and Concept of entities … Marcel Decker “Natural Language Processing” , in Encyclopedia of Library and Information Science in 2001 [2] Min-kyoung Kim, Han-joon … Related articles All 2 versions Cite Save More
Regular Language Induction with Grammar-based Classifier System O Unold – researchgate.net … GCS was applied with success to natural language processing (Unold, 2007a), biological promoter regions (Unold, 2007b), and toy grammar (Unold … Cocke Younger Kasami (CYK) parser, which operates in (n3) time (Younger, 1967), is used to parse sentences from the corpus. … Related articles All 5 versions Cite Save More
Converting CCGs into Typed Feature Structure Grammars HU Krieger, B Kiefer, S Müller – Head-Driven Phrase Structure Grammar – stanford.edu Page 1. Hans-Ulrich Krieger and Bernd Kiefer German Research Center for Artificial Intelligence (DFKI) Stuhlsatzenhausweg 3, D-66123 Saarbrücken, Germany {krieger,kiefer}@dfki.de Proceedings of the HPSG 2011 Conference … Related articles All 9 versions Cite Save More
Grammar Mining. S Nijssen, L De Raedt – SDM, 2009 – SIAM … 1 Introduction In many application areas, such as bioinformatics and natural language processing, scripting languages that provide facilities for dealing with … The CYK parser is one of the simplest chart parsers, which makes it more convenient to introduce the ideas behind our … Related articles All 10 versions Cite Save
The University of Cambridge Russian-English System at WMT13 JPAW TongXiao, AGFF WilliamByrne – aclweb.org … Decoding is guided by a CYK parser based on a synchronous context-free grammar induced from automatic word alignments (Chiang … In Proceedings of the 2008 Conference on Empiri- cal Methods in Natural Language Processing, pages 725–734, Honolulu, Hawaii, October. … Related articles All 8 versions Cite Save More
Converting CCGs into Typed Feature Structure Grammars Hans-Ulrich Krieger and Bernd Kiefer German Research Center for Artificial Intelligence (DFKI) … S Müller – 2011 CSLI Publications http://csli-publications. stanford … – dosen.narotama.ac.id Page 109. Converting CCGs into Typed Feature Structure Grammars Hans-Ulrich Krieger and Bernd Kiefer German Research Center for Artificial Intelligence (DFKI) Stuhlsatzenhausweg 3, D-66123 Saarbrücken, Germany 1krieger, kieferl@ dfki. … Related articles All 4 versions Cite Save More
Unsupervised induction of dependency structures using Probabilistic Bilexical Grammars MA Domínguez, G Infante-Lopez – Natural Language …, 2011 – ieeexplore.ieee.org … b) K-Best PBG Parser.: Since PBGs are a particular case of probabilistic context free grammars, our parser for PBG is based on an implementation of a k-best CYK parser for Chomsky Normal Form PCFGs … [2] D. Klein, “The unsupervised learning of natural language structure,” Ph … Related articles Cite Save
Computer Assisted Creation of Items for Scrambled Sentence Tests C Liu, C Huang, Y Sun, W Kuo – icce2009.ied.edu.hk … Techniques that were originally designed for natural language processing (NLP) have proved to be instrumental for applications for computer assisted language learning (CALL) [1, 3, 7]. In this paper, we … It is easy to implement a chart parser (aka CYK parser; [6]) for this purpose … Related articles All 4 versions Cite Save More
Indexing spoken documents with hierarchical semantic structures: Semantic tree-to-string alignment models X Zhu, C Cherry, G Penn – … Natural Language …, 2011 – nparc.cisti-icist.nrc-cnrc.gc.ca … Proceedings of the 5th International Joint Conference on Natural Language Processing, pages 509–517, Chiang Mai, Thailand, November 8 – 13, 2011. … A dynamic programming approach, eg, that used in a con- ventional CYK parser, can be adapted to solve this problem, in … Cited by 2 Related articles All 7 versions Cite Save More
Finite-state chart constraints for reduced complexity context-free parsing pipelines B Roark, K Hollingshead, N Bodenstab – Computational Linguistics, 2012 – MIT Press Cited by 4 Related articles All 8 versions Cite Save
Probabilistic Tree-generating Binary Grammars P Skórzewski, K Jassem – Poznan Studies in Contemporary Linguistics – degruyter.com … For PCFG, one can define notions of tree probability and sentence probability. This makes PCFG helpful in solving vari- ous natural language problems: – Algorithms for finding the most probable parse tree are useful for disambig- uation of sentence meaning (Plaehn 2005). … Cite Save
Inducing Document Plans for Concept-to-text Generation I Konstas, M Lapata – aclweb.org … The latter is essentially a PCFG which captures both the structure of the input database and the way it renders into natural language. … Konstas and Lapata (2012) use a modified version of the CYK parser (Kasami, 1965; Younger, 1967) to find ˆg. … Cited by 1 Related articles All 5 versions Cite Save More
Learning context-free grammar using improved tabular representation O Unold, M Jaworski – Applied Soft Computing, 2010 – Elsevier … It is also possible to extend the CYK algorithm to handle some context-free grammars which are not in CNF [27]. The CYK parser considers which nonterminals can be used to derive substrings of the input, beginning with shorter strings and moving up to longer strings. … Cited by 7 Related articles All 3 versions Cite Save
Probabilistic estimation of probabilistic syntactic models JA Sánchez – videolectures.net … 1.1 Introduction “Computational Linguistics” deals with the most difficult communication process: Natural Language Multimedia & Technologies Multimodality … Page 10. 1.2 Syntactic models and Parsing Knowledge levels in Natural Language: Morphology: word structure Syntax: … Related articles Cite Save More
Improving Turkish Software Metric Tool (TSMC) with new metrics M Turan – 2009 – cse.iku.edu.tr … BC (bounded context) parsing ? LR parser (Left-to-right, Rightmost derivation) o Simple LR (SLR) parser o LALR parser o Canonical LR (LR(1)) parser o GLR parser o CYK parser (Reference from project1.) Page 13. 13 “We use XML structure to record metric data’s. … Related articles Cite Save More
Are Very Large Context-Free Grammars Tractable? P Boullier, B Sagot – Trends in Parsing Technology, 2010 – Springer … Email: pierre.boullier@inria.fr. Benoît Sagot. Email: benoit.sagot@inria.fr. Abstract. More and more often, in real-word natural language processing (NLP) applications based upon grammars, these grammars are no longer written by hand, but are automatically generated. … Cited by 2 Related articles All 34 versions Cite Save
A Tool for Model-Based Language Specification L Quesada, F Berzal, JC Cubero – arXiv preprint arXiv:1111.3970, 2011 – arxiv.org … rules [2, 12]. A general-purpose dynamic programming algorithm for parsing context-free grammars was independently de- veloped by Cocke [7], Younger [57], and Kasami [30]: the CYK parser. This general-purpose algorithm … Related articles All 5 versions Cite Save
Algorithm for Analysis and Translation of Sentence Phrases R Lacko – is.muni.cz … iii Page 4. Abstract This thesis proposes a library with an algorithm capable of translating objects described by natural language phrases into their formal representations in an object model. … Keywords Natural language, syntax analysis, chart parsing, interpreting, MotiveQuery v … Cite Save More
Application of Tree Transducers in Statistical Machine Translation M Razmara – 2011 – cs.sfu.ca … Automatic text translation, commonly called machine translation, is one of the oldest yet unsolved problems of natural language processing and artificial intelligence. Hand-crafted … But string-based models were not able to capture many of the natural language properties. … Cited by 1 Related articles All 3 versions Cite Save More
Handbook of Pattern Recognition and Computer Vision CH Chen, LF Pau, PSP Wang – World Scientific … 648 crossing number 458, 465 crossover 21, 79, 91 cues 743 curvature 601, 872 curve segmentation 574 Cushing’s syndrome patterns 662 CYK parser 200 … naming tasks 864 error rates 865 narrow-band filtering 561 natural language 763 processing 570 navigation 771, 807 … Cited by 1 Cite Save
Multiple Context-Free Grammars and Linear Context-Free Rewriting Systems PDDL Kallmeyer – Parsing Beyond Context-Free Grammars, 2010 – Springer … Since discontinuities occur frequently in natural languages, MCFG and LCFRS are interesting formalisms for natural language processing. … The CYK parsers presented in Section 7.1 are formulated in terms of MCFG and LCFRS while in Section 7.3, we notate the MCFG as a … Related articles All 2 versions Cite Save
A non-contiguous tree sequence alignment-based model for statistical machine translation J Sun, M Zhang, CL Tan – … Joint Conference on Natural Language …, 2009 – dl.acm.org … non-contiguous rule is no greater than . 4 The Pisces decoder We implement our decoder Pisces by simulating the span based CYK parser constrained by the rules of SncTSSG. The decoder translates each span iteratively in … Cited by 13 Related articles All 17 versions Cite Save
Fast learning of grammar production probabilities in radar electronic support G Latombe, E Granger, FA Dilkes – Aerospace and Electronic …, 2010 – ieeexplore.ieee.org … increased memory complexity. For example, Fujisaki et al. [12] used a CYK parser to find the parse trees or the most probable parse trees of the sequences and then directly applied either the IO or the VS algorithm. Based on this … Cited by 5 Related articles All 5 versions Cite Save
Intent Inference and Detection of Anomalous Trajectories: A Metalevel Tracking Approach V KRISHNAMURTHY – Integrated Tracking, Classification, and …, 2012 – books.google.com … The recovery of the most likely parse tree ? (x) is computed using the probabilistic CYK parser [22] that is a dynamic programming algorithm similar to the Viterbi algorithm used for maximum likelihood sequence estimation in HMMs. … Related articles Cite Save
Learning effective grammar rules for machine translation L Fang – 2013 – urresearch.rochester.edu … languages, and closely tied machine translation research with the research on natural language taggers and parsers. The performance of syntax-based machine translation … GOAL : [S,0,n] Figure 1.6: Deduction for CYK parser INITIALIZATION : (A ? ?) [A ? ·?, i, i] … Cite Save More
Grammar Induction with Prototypes Derived from Interlinear Text R Georgi – 2009 – students.washington.edu … Because inside-outside re-estimation and distributional approaches model slightly differ- ent aspects of natural language yet aim to achieve the same goal, combining the two may produce better results than running each individually. Page 19. 3 1.2 Prototyping as Bootstrapping … Related articles Cite Save More
A Global Model for Concept-to-Text Generation I Konstas, M Lapata – Journal of Artificial Intelligence Research, 2013 – jair.org … They present a novel SCFG forest-to-string generation algorithm, that captures the correspondence between natural language and logical form represented by ??hybrid trees. … We use a modified version of the CYK parser (Kasami, 1965; Younger, 1967) to find ˆg. … Cited by 1 Related articles All 2 versions Cite Save More
Visualization, Search and Analysis of Hierarchical Translation Equivalence in Machine Translation Data GM de Buy Wenniger, K Sima’an – The Prague Bulletin of …, 2014 – degruyter.com … These alternative HATs can be efficiently computed and stored as a chart using a CYK-parser like chart parsing algorithm that … In Proceedings of Human Language Technology Conference and Conference on Empirical Methods in Natural Language Processing, pages 803–810 … Cite Save
Joint models for concept-to-text generation I Konstas – 2014 – era.lib.ed.ac.uk … 1.2. Thesis Contributions 3 they will be presented in natural language (surface realisation). Another issue is that … it into a probabilistic context-free grammar. Then we formulate several decoding algorithms based on the CYK parser (Kasami, 1965; Younger, 1967). We show … Cite Save
Discriminative Learning Approaches for Statistical Processing of Chinese Y Zhang – 2009 – cl.cam.ac.uk … 76 x Page 11. 5.3 An illustration of the cyk parser . . . . . … Chapter 1 Introduction Natural language processing (nlp), or computational linguistics, is the study of artificial intelligence concerning the processing of human languages. It facilitates communication not only between hu- … Related articles All 3 versions Cite Save More
Interface Issues in Robot Scrub Nurse Design A Agovic – 2011 – conservancy.umn.edu … the various components for assistant robots. Furthermore we contribute novel insights in the design of grasp planning methods, visual tracking methods and natural language dialogue systems. iv Page 7. Contents Acknowledgements … 10 2.3 Natural Language Processing . . . . … Related articles All 2 versions Cite Save More
Grammatical Approaches to Problems in RNA Bioinformatics CH zu Siederdissen – tbi.univie.ac.at … 26 3.1.2 Formal Grammars . . . . . 26 3.1.3 The CYK Parser . . . . . 29 3.1.4 Syntactic, Structural, and Semantic Ambiguity . . . . . 31 3.2 Algebraic Dynamic Programming (ADP) . . . . … Related articles All 5 versions Cite Save More
[BOOK] RNA Structural Motif Discovery using Probabilistic Tree Adjoining Grammars. E Bahrami Samani – 2009 – dspace.hil.unb.ca Page 1. RNA Structural Motif Discovery using Probabilistic Tree Adjoining Grammars by Emad Bahrami Samani Bachelor of Computer Engineering, Amirkabir University of Technology, Tehran, Iran, 2007 A THESIS SUBMITTED … Related articles Cite Save