Computational Grammar TheoryAbed Kadaan · research program

Bibliography

55 entries: 46 metadata verified, 8 secondary sources only, 1 unverified. Metadata verified means authors, title, venue and year were checked against publisher, DBLP or institutional records; it does not mean the full text was read. Each entry states what was consulted.

  1. Adelson-Velsky & Landis 1962 G. M. Adelson-Velsky, E. M. Landis (1962). An algorithm for the organization of information. Doklady Akademii Nauk SSSR (English translation in Soviet Mathematics Doklady). Secondary sources onlyJournal details from general knowledge; not verified.
  2. Agrawal et al. 1989 R. Agrawal, A. Borgida, H. V. Jagadish (1989). Efficient management of transitive relationships in large data and knowledge bases. Proc. ACM SIGMOD 1989, pp. 253–262. doi:10.1145/67544.66950. Metadata verified
  3. Aspvall et al. 1979 B. Aspvall, M. F. Plass, R. E. Tarjan (1979). A linear-time algorithm for testing the truth of certain quantified Boolean formulas. Information Processing Letters 8(3):121–123. doi:10.1016/0020-0190(79)90002-4. Metadata verified
  4. Baier & Katoen 2008 C. Baier, J.-P. Katoen (2008). Principles of Model Checking. MIT Press (ISBN 978-0-262-02649-9). Metadata verifiedCited for the general product of Markov chains with automata; the specific section was not located.
  5. Barrett et al. 2000 C. Barrett, R. Jacob, M. Marathe (2000). Formal-language-constrained path problems. SIAM Journal on Computing 30(3):809–837. doi:10.1137/S0097539798337716. Metadata verified
  6. Bellman 1958 R. Bellman (1958). On a routing problem. Quarterly of Applied Mathematics 16(1):87–90. Metadata verified
  7. Bender & Farach-Colton 2000 M. A. Bender, M. Farach-Colton (2000). The LCA problem revisited. Proc. LATIN 2000, LNCS 1776, pp. 88–94. Metadata verified
  8. Bianchini et al. 2005 M. Bianchini, M. Gori, F. Scarselli (2005). Inside PageRank. ACM Transactions on Internet Technology 5(1):92–128. doi:10.1145/1052934.1052938. Metadata verified
  9. Bille et al. 2011 P. Bille, G. M. Landau, R. Raman, K. Sadakane, S. R. Satti, O. Weimann (2011). Random access to grammar-compressed strings. Proc. 22nd ACM-SIAM SODA, pp. 373–389. link. Metadata verifiedA journal version (SIAM J. Comput.) exists; its volume and pages were not verified.
  10. Blumensath & Grädel 2000 A. Blumensath, E. Grädel (2000). Automatic structures. Proc. 15th IEEE LICS, pp. 51–62. Metadata verified
  11. Brin & Page 1998 S. Brin, L. Page (1998). The anatomy of a large-scale hypertextual Web search engine. Computer Networks and ISDN Systems 30:107–117. Metadata verified
  12. Buneman et al. 2003 P. Buneman, M. Grohe, C. Koch (2003). Path queries on compressed XML. Proc. 29th VLDB, pp. 141–152. doi:10.1016/B978-012722442-8/50021-5. Metadata verified
  13. Charikar et al. 2005 M. Charikar, E. Lehman, D. Liu, R. Panigrahy, M. Prabhakaran, A. Sahai, A. Shelat (2005). The smallest grammar problem. IEEE Transactions on Information Theory 51(7):2554–2576. doi:10.1109/TIT.2005.850116. Metadata verified
  14. Cohen et al. 2003 E. Cohen, E. Halperin, H. Kaplan, U. Zwick (2003). Reachability and distance queries via 2-hop labels. SIAM Journal on Computing 32(5):1338–1355. doi:10.1137/S0097539702403098. Metadata verified
  15. Cormen et al. 2022 T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein (2022). Introduction to Algorithms, 4th edition. MIT Press (ISBN 978-0-262-04630-5). Metadata verified
  16. Darwiche & Marquis 2002 A. Darwiche, P. Marquis (2002). A knowledge compilation map. Journal of Artificial Intelligence Research 17:229–264. doi:10.1613/jair.989. Metadata verified
  17. Dijkstra 1959 E. W. Dijkstra (1959). A note on two problems in connexion with graphs. Numerische Mathematik 1:269–271. doi:10.1007/BF01386390. Metadata verified
  18. Downey et al. 1980 P. J. Downey, R. Sethi, R. E. Tarjan (1980). Variations on the common subexpression problem. Journal of the ACM 27(4):758–771. Metadata verified
  19. Epstein et al. 1992 D. B. A. Epstein, J. W. Cannon, D. F. Holt, S. V. F. Levy, M. S. Paterson, W. P. Thurston (1992). Word Processing in Groups. Jones and Bartlett (later A K Peters). Metadata verified
  20. Fenwick 1994 P. M. Fenwick (1994). A new data structure for cumulative frequency tables. Software: Practice and Experience 24(3):327–336. doi:10.1002/spe.4380240306. Metadata verified
  21. Ford 1956 L. R. Ford Jr. (1956). Network flow theory. RAND Corporation Paper P-923. Secondary sources onlyIts role as an origin of the Bellman–Ford algorithm is commonly stated but was not verified here.
  22. Harel & Tarjan 1984 D. Harel, R. E. Tarjan (1984). Fast algorithms for finding nearest common ancestors. SIAM Journal on Computing 13(2):338–355. doi:10.1137/0213024. Metadata verified
  23. Haveliwala & Kamvar 2003 T. Haveliwala, S. Kamvar (2003). The second eigenvalue of the Google matrix. Technical report, Stanford University. Secondary sources only
  24. Haveliwala 2002 T. H. Haveliwala (2002). Topic-sensitive PageRank. Proc. 11th International World Wide Web Conference (WWW 2002). link. Metadata verified
  25. Hoare 1962 C. A. R. Hoare (1962). Quicksort. The Computer Journal 5(1):10–16. doi:10.1093/comjnl/5.1.10. Metadata verifiedSources disagree on the last page (15 or 16).
  26. Italiano 1986 G. F. Italiano (1986). Amortized efficiency of a path retrieval data structure. Theoretical Computer Science 48:273–281. Metadata verified
  27. Jacobson 1989 G. Jacobson (1989). Space-efficient static trees and graphs. Proc. 30th IEEE FOCS, pp. 549–554. Metadata verified
  28. Kahn 1962 A. B. Kahn (1962). Topological sorting of large networks. Communications of the ACM 5(11):558–562. doi:10.1145/368996.369025. Secondary sources only
  29. Kamvar et al. 2003 S. Kamvar, T. Haveliwala, C. Manning, G. Golub (2003). Exploiting the block structure of the Web for computing PageRank. Technical Report 2003-17, Stanford University. Secondary sources only
  30. Karp & Lipton 1980 R. M. Karp, R. J. Lipton (1980). Some connections between nonuniform and uniform complexity classes. Proc. 12th ACM STOC, pp. 302–309. Secondary sources onlyThe improvement of the collapse to the second level is commonly credited to Sipser (secondary sources).
  31. Khoussainov & Nerode 1995 B. Khoussainov, A. Nerode (1995). Automatic presentations of structures. Logic and Computational Complexity, LNCS 960. UnverifiedKnown through citing papers only; pages not confirmed.
  32. Kleitman & Rothschild 1975 D. J. Kleitman, B. L. Rothschild (1975). Asymptotic enumeration of partial orders on a finite set. Transactions of the AMS 205:205–220. Metadata verified
  33. Knuth 1968 D. E. Knuth (1968). Semantics of context-free languages. Mathematical Systems Theory 2(2):127–145. doi:10.1007/BF01692511. Metadata verified
  34. Knuth et al. 1977 D. E. Knuth, J. H. Morris Jr., V. R. Pratt (1977). Fast pattern matching in strings. SIAM Journal on Computing 6(2):323–350. doi:10.1137/0206024. Metadata verified
  35. Kozen 1997 D. Kozen (1997). Kleene algebra with tests. ACM Transactions on Programming Languages and Systems 19(3):427–443. doi:10.1145/256167.256195. Metadata verified
  36. Kruskal 1956 J. B. Kruskal (1956). On the shortest spanning subtree of a graph and the traveling salesman problem. Proceedings of the AMS 7:48–50. doi:10.1090/S0002-9939-1956-0078686-7. Metadata verified
  37. Langville & Meyer 2004 A. N. Langville, C. D. Meyer (2004). Deeper inside PageRank. Internet Mathematics 1(3):335–380. doi:10.1080/15427951.2004.10129091. Metadata verified
  38. Langville & Meyer 2006 A. N. Langville, C. D. Meyer (2006). Google's PageRank and Beyond: The Science of Search Engine Rankings. Princeton University Press (ISBN 978-0-691-12202-1). Metadata verified
  39. Lewis et al. 2020 P. Lewis, E. Perez, A. Piktus, F. Petroni, V. Karpukhin, N. Goyal, H. Küttler, M. Lewis, W. Yih, T. Rocktäschel, S. Riedel, D. Kiela (2020). Retrieval-augmented generation for knowledge-intensive NLP tasks. Advances in Neural Information Processing Systems 33. link. Metadata verifiedPage numbers not verified.
  40. Lohrey 2015 M. Lohrey (2015). Grammar-based tree compression. Proc. DLT 2015 (LNCS). doi:10.1007/978-3-319-21500-6_3. Metadata verified
  41. Malkov & Yashunin 2020 Yu. A. Malkov, D. A. Yashunin (2020). Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs. IEEE Transactions on Pattern Analysis and Machine Intelligence. doi:10.1109/TPAMI.2018.2889473. Secondary sources onlyDOI and arXiv verified; the journal issue year was not confirmed.
  42. Mendelzon & Wood 1995 A. O. Mendelzon, P. T. Wood (1995). Finding regular simple paths in graph databases. SIAM Journal on Computing 24(6):1235–1258. Metadata verified
  43. Page et al. 1999 L. Page, S. Brin, R. Motwani, T. Winograd (1999). The PageRank citation ranking: Bringing order to the Web. Technical Report 1999-66, Stanford InfoLab. link. Secondary sources only
  44. Prim 1957 R. C. Prim (1957). Shortest connection networks and some generalizations. Bell System Technical Journal 36(6):1389–1401. doi:10.1002/j.1538-7305.1957.tb01515.x. Metadata verified
  45. Reps 1998 T. Reps (1998). Program analysis via graph reachability. Information and Software Technology 40(11–12):701–726. doi:10.1016/S0950-5849(98)00093-7. Metadata verified
  46. Schieber & Vishkin 1988 B. Schieber, U. Vishkin (1988). On finding lowest common ancestors: simplification and parallelization. SIAM Journal on Computing 17(6):1253–1262. doi:10.1137/0217079. Metadata verified
  47. Sun et al. 2011 Y. Sun, J. Han, X. Yan, P. S. Yu, T. Wu (2011). PathSim: Meta path-based top-k similarity search in heterogeneous information networks. Proceedings of the VLDB Endowment 4(11):992–1003. Metadata verified
  48. Tarjan 1972 R. E. Tarjan (1972). Depth-first search and linear graph algorithms. SIAM Journal on Computing 1(2):146–160. doi:10.1137/0201010. Metadata verified
  49. Tarjan 1975 R. E. Tarjan (1975). Efficiency of a good but not linear set union algorithm. Journal of the ACM 22(2):215–225. Metadata verified
  50. Tarjan 1981a R. E. Tarjan (1981). A unified approach to path problems. Journal of the ACM 28(3):577–593. Metadata verified
  51. Tarjan 1981b R. E. Tarjan (1981). Fast algorithms for solving path problems. Journal of the ACM 28(3):594–614. doi:10.1145/322261.322273. Metadata verified
  52. Vaswani et al. 2017 A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, Ł. Kaiser, I. Polosukhin (2017). Attention is all you need. Advances in Neural Information Processing Systems 30, pp. 5998–6008. Metadata verified
  53. Verbin & Yu 2013 E. Verbin, W. Yu (2013). Data structure lower bounds on random access to grammar-compressed strings. Proc. CPM 2013 (LNCS). link. Metadata verifiedVenue confirmed via arXiv and citing papers.
  54. Williams 1964 J. W. J. Williams (1964). Algorithm 232: Heapsort. Communications of the ACM 7(6):347–348. Metadata verified
  55. Yannakakis 1990 M. Yannakakis (1990). Graph-theoretic methods in database theory. Proc. 9th ACM PODS, pp. 230–242. doi:10.1145/298514.298576. Metadata verified