2021 Fall
Welcome to the homepage of CSE 645: Seminar in Languages (Fall 2021)!
General Information
Course description: We will read papers and discuss research ranging from high-level specifications (such as logic, rules, and sets) to algorithms and methods for efficient implementations of programming languages, with a wide range of applications.
Everyone is welcome. If you are enrolled in the class, you are expected to attend a majority of the meetings and present a paper.
Hours: Thursdays, 11:30AM-12:50PM ET, in New Computer Science 220 and on Zoom https://stonybrook.zoom.us/j/94298584108?pwd=OXRLemROdk8xOHY3NXFRV2xjQmhVUT09
Instructors: Annie Liu, CR Ramakrishnan, Michael Kifer, David Warren, and Paul Fodor (contact: paul.fodor@stonybrook.edu).
Previous semesters: see the list to the left.
Schedule
8/26/2021 Organizational meeting.
9/2/2021 Paul: Logic programming competitions, role mining problem (https://arxiv.org/pdf/2008.07901.pdf Appendix B, Page 3, MinRoleAssignments, WithHierarchy) and some Prolog and ASP solutions. (Appendices C-H are solutions to the overall programming challenge.)
9/9/2021 Anthony: Leibniz: A Generics-Based Expression Simplifier. Maple Trans. 2021. Dry run for presentation at the Maple conference.
9/16/2021 General discussions: Skyscraper puzzle (https://www.puzzle-skyscrapers.com/) and a puzzling:) solution in Clingo; roll-cutting problem and a solution in AMPL (https://www.youtube.com/watch?v=CAmd6cdEfLk).
9/23/2021 Datalog perspectives at ICLP 2021 (https://iclp2021.dcc.fc.up.pt/index-program.html#program, 11:30 EST exactly our seminar time, students can register for free), video (https://www.youtube.com/watch?v=dmQjMkHSuSs).
9/30/2021 Conference report and comments, led by David: Interesting talks and events from ICLP 2021 (Invited talks https://www.youtube.com/playlist?list=PLEoSo8qG5x2krs4YzI-oCJYFGu1cinmvU).
10/7/2021 Stuart Russell invited talk replay and discussion: Combining probability and first-order logic (video https://www.youtube.com/watch?v=b9YC9PLOWJE). CR leads the discussions after.
10/14/2021 Matthew Castellana will discuss Bouma W, Fudos I, Hoffmann C, Cai J, and Paige R. Geometric constraint solver. Computer-Aided Design, 27(6):487-501, 1995. (Definition of key terms, found by Christopher)
10/21/2021 David will discuss Frisch, Alan M., et al. Essence: A constraint language for specifying combinatorial problems, Constraints 13.3 (2008): 268-306. (slides)
10/28/2021 Annie will discuss Recursive Rules with Aggregation: A Simple Unified Semantics, accepted by Logic Foundations of Computer Science (LFCS) 2022 (will focus on ideas with examples, instead of formal parts in Sec 3-5, though mostly the latter fits in the page limit of LFCS).
11/4/2021 Akshay Nair will discuss Frisch, Alan M., et al. The rules of constraint modelling, IJCAI, 2005. (slides)
11/11/2021 Yuheng will discuss Akgun, Ozgur, et al. Conjure revisited: Towards automated constraint modelling, arXiv preprint arXiv:1109.1774 (2011). (slides)
11/18/2021 Giorgian will discuss Gent, Ian P., Ian Miguel, and Andrea Rendl. Tailoring solver-independent constraint models: A case study with Essence′ and Minion, International Symposium on Abstraction, Reformulation, and Approximation. Springer, Berlin, Heidelberg, 2007. (slides)
11/25/2021 Thanksgiving break
12/2/2021 Neng-Fa Zhou: Modeling and Solving Graph Synthesis Problems Using SAT-Encoded Reachability Constraints in Picat, ICLP 2021 Technical Communications, plus a problem from ICLP 2021 programming contest. (slides)
Papers (1-4 and 7 are already covered)
Below are some candidate papers to discuss:
1. an introduction of Essence language
Frisch, Alan M., et al. "Essence: A constraint language for specifying combinatorial problems" Constraints 13.3 (2008): 268-306.
2. technique paper on Conjure, a system that translate Essence to Essence' which takes only atomic variables, that is used in most of the solvers
Frisch, Alan M., et al. "The rules of constraint modelling." IJCAI. 2005.
3. an improved implementation of Conjure
Akgun, Ozgur, et al. "Conjure revisited: Towards automated constraint modelling." arXiv preprint arXiv:1109.1774 (2011).
4. Tailor system, transform from the solver independent Essence' to a particular constraint solver
Gent, Ian P., Ian Miguel, and Andrea Rendl. "Tailoring solver-independent constraint models: A case study with Essence′ and Minion." International Symposium on Abstraction, Reformulation, and Approximation. Springer, Berlin, Heidelberg, 2007.
5. Savile Row, a multi-pass term rewriting system, the frontend reads a model in the Essence Prime language into an AST, several backends target a range of solvers
Nightingale, Peter, et al. "Automatically improving constraint models in Savile Row." Artificial Intelligence 251 (2017): 35-61.
6. a recent survey paper on reformulation that might be helpful
Vo, Huu-Phuc. "Reformulations of Constraint Satisfaction Problems: A Survey." (2020).
Neng-Fa Zhou, Modeling and Solving Graph Synthesis Problems Using SAT-Encoded Reachability Constraints in Picat, ICLP 2021 Technical Communications
Benjamin Bichsel, Maximilian Baader, Timon Gehr, Martin Vechev. "Silq: A High-Level Quantum Language with Safe Uncomputation and Intuitive Semantics". PLDI 2020. https://dl.acm.org/doi/pdf/10.1145/3385412.3386007
Kochenberger et al. The unconstrained binary quadratic programming problem: a survey
Glover, Kochenberger, Du. Quantum Bridge Analytics I: A Tutorial on Formulating and Using QUBO Models
https://arxiv.org/pdf/1811.11538.pdf