CYK algorithm: Difference between revisions

Revision as of 16:46, 17 November 2014

Revision as of 00:13, 19 November 2014

Line 104:

{{Reflist}}

{{Refbegin}}

* {{citationcite techreport |last1=Cocke |first1=John |author1-linkauthorlink1=John Cocke |last2=Schwartz |first2=Jacob T. |year=1970 |date=April 1970 |title=Programming languages and their compilers: Preliminary notes |journaledition=Technical2nd reportrevised |publisher=[[Courant Institute of Mathematical Sciences|CIMS]], [[New York University|NYU]] |url=http://www.softwarepreservation.org/projects/FORTRAN/CockeSchwartz_ProgLangCompilers.pdf}}

* {{citationcite techreport |last1=Kasami |first1=T. |author1-linkauthorlink1=Tadao Kasami |year=1965 |title=An efficient recognition and syntax-analysis algorithm for context-free languages |journalnumber=Scientific report AFCRL-65-758 |publisher=[[Air Force Cambridge Research Lab Laboratories|___location=[[Bedford, MAAFCRL]]}}

* {{citationcite journal |last1=Younger |first1=Daniel H. |year=1967 |date=February 1967 |title=Recognition and parsing of context-free languages in time ''n''³ |journal=[[Information and Computation|Inform. Control]] |volume=10 |issue=2 |pages=189–208 |doi=10.1016/s0019-9958(67)80007-x}}

* {{citationcite book |last1=Knuth |first1=Donald E. |author1-linkauthorlink1=Donald Knuth |title=The Art of Computer Programming Volume 2: Seminumerical Algorithms |publisher=Addison-Wesley Professional |edition=3rd |date=November 14, 1997 |isbn=0-201-89684-2 |pages=501 }}

*{{cite journal |last1=Lange |first1=Martin |last2=Leiß |first2=Hans |title=To CNF or not to CNF? An Efficient Yet Presentable Version of the CYK Algorithm |year=2009 |journal=Informatica Didactica |volume=8 |url=http://www.informatica-didactica.de/cmsmadesimple/index.php?page=LangeLeiss2009}}

* {{Citation

*{{cite book |last1=Sipser |first1=Michael |authorlink1=Michael Sipser |title=Introduction to the Theory of Computation |publisher=IPS |year=1997 |edition=1st |page=99 |isbn=0-534-94728-X}}

|last1=Lange

*{{cite journal |last1=Lee |first1=Lillian |title=Fast context-free grammar parsing requires fast Boolean matrix multiplication |journal=[[Journal of the ACM|J. ACM]] |volume=49 |issue=1 |pages=1–15 |year=2002 |doi=10.1145/505241.505242}}

|first1=Martin

*{{citationcite journal |last1=Valiant |first1=Leslie G. |author1-linkauthorlink1=Leslie Valiant |title=General context-free recognition in less than cubic time |journal=[[Journal of Computer and System Sciences|J. Comput. Syst. Sci.]] |volume=10 |issue=2 |year=1975 |pages=308–314 |doi=10.1016/s0022-0000(75)80046-8}}

|last2=Leiß

*{{citationcite journal |last1=Lang |first1=Bernard |title=Recognition can be harder than parsing |journal=[[Computational Intelligence (journal)|Comput. Intell.]] |year=1994 |volume=10 |issue=4 |pages=486–494 |id={{citeseerx|10.1.1.50.6982}} |doi=10.1111/j.1467-8640.1994.tb00011.x}}

|first2=Hans

|title=To CNF or not to CNF? An Efficient Yet Presentable Version of the CYK Algorithm

|year=2009

|journal=Informatica Didactica

|volume=8

|url=http://www.informatica-didactica.de/cmsmadesimple/index.php?page=LangeLeiss2009

}}

*{{Citation

|last1=Sipser

|first1=Michael

|author1-link=Michael Sipser

|title=Introduction to the Theory of Computation

|publisher=IPS

|year=1997

|edition=1st

|page=99

|isbn=0-534-94728-X

}}

*{{Citation

|last1=Lee

|first1=Lillian

|title=Fast context-free grammar parsing requires fast Boolean matrix multiplication

|journal=[[Journal of the ACM|J. ACM]]

|volume=49

|issue=1

|pages=1–15

|year=2002

|doi=10.1145/505241.505242

}}

*{{citation |last1=Valiant |first1=Leslie G. |author1-link=Leslie Valiant |title=General context-free recognition in less than cubic time |journal=[[Journal of Computer and System Sciences|J. Comput. Syst. Sci.]] |volume=10 |issue=2 |year=1975 |pages=308–314 |doi=10.1016/s0022-0000(75)80046-8}}

*{{citation |last1=Lang |first1=Bernard |title=Recognition can be harder than parsing |journal=[[Computational Intelligence (journal)|Comput. Intell.]] |year=1994 |volume=10 |issue=4 |pages=486–494 |id={{citeseerx|10.1.1.50.6982}} |doi=10.1111/j.1467-8640.1994.tb00011.x}}

{{Refend}}