2016 Fall

Welcome to the homepage of CSE645 (Fall 2016) Seminar in Languages!

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, with applications in semantic web, program analysis, security, and services.

Instructors: Annie Liu, CR Ramakrishnan, Michael Kifer, David Warren, and Paul Fodor (contact: paul.fodor@stonybrook.edu).

Hours: Thursdays, 11:30AM-12:50PM, in New Computer Science Department room 220.

If you are enrolled in the class, you must attend at least 50% of the meetings and to present a paper during the semester.

Papers

We will select papers from the following list (don't have to cover all) and possibly other interesting ones as they come up.

Cook SA. The complexity of theorem-proving procedures. InProceedings of the third annual ACM symposium on Theory of computing 1971 May 3 (pp. 151-158). ACM.

http://www.chell.co.uk/media/product/_master/1/files/cook_complexity_of_theorem_proving_procedures_19712.pdf

Mahmoud Abo Khamis, Hung Q. Ngo, Atri Rudra (LogicBlox).

FAQ: Questions asked Frequently.

PODS 2016.

http://arxiv.org/abs/1504.04044

Abstract rewriting approach to solve Datalog programs.

Fernando Tarin Morales, Fuyuki Isihikawa, Shinichi Honiden.

DBLP 2015.

http://dl.acm.org/ft_gateway.cfm?id=2815076&ftid=1636453&dwn=1&CFID=832842527&CFTOKEN=73347840

Inference and learning in probabilistic logic programs using weighted Boolean formulas.

Fierens, Daan, Van den Broeck, Guy, Renkens, Joris, Shterionov, Dimitar, Gutmann, Bernd, Thon, Ingo, Janssens, Gerda, De Raedt, Luc.

In Theory and Practice of Logic Programming, 15 (3): 358-401, 2015

https://lirias.kuleuven.be/handle/123456789/392821

aspartame: Solving Constraint Satisfaction Problems with Answer Set Programming

Mutsunori Banbara, Martin Gebser, Katsumi Inoue, Max Ostrowski, Andrea Peano, Torsten Schaub, Takehide Soh, Naoyuki Tamura and Matthias Weise.

In Proceedings of Answer Set Programming and Other Computing Paradigms (ASPOCP 2013), 6th International Workshop, August 25, 2013, Istanbul, Turkey.

http://www.cs.uni-potsdam.de/wv/pdfformat/bageinospescsotawe15a.pdf

Rewriting recursive aggregates in answer set programming: back to monotonicity

Mario Alviano, Wolfgang Faber and Martin Gebser. In ICLP 2015.

http://arxiv.org/pdf/1507.03923v1.pdf

Complexity and Compilation of GZ-Aggregates in Answer Set Programming

Mario Alviano and Nicola Leone. In ICLP 2015.

http://arxiv.org/pdf/1507.03922v1.pdf

Inference in the FO(C) Modelling Language.

Bart Bogaerts, Joost Vennekens, Marc Denecker, and Jan Van den Bussche.

In ECAI 2014.

http://arxiv.org/pdf/1404.6368v1.pdf

Constraint Propagation for First-Order Logic and Inductive Definitions,

Johan Wittocx, Marc Denecker, Maurice Bruynooghe.

ACM Transactions on Computational Logic, 2013.

https://lirias.kuleuven.be/bitstream/123456789/369791/1/final.pdf

Computing most probable worlds of action probabilistic logic programs: scalable estimation for 10^30,000 worlds,

Samir Khuller, M Vanina Martinez, Dana Nau, Amy Sliva, Gerardo I Simari, Venkatramanan Siva Subrahmanian,

Annals of Mathematics and Artificial Intelligence, 2007,

http://www.ccs.neu.edu/home/asliva/papers/somaMPW-amai07.pdf

A Pattern Calculus for Rule Languages: Expressiveness, Compilation, and Mechanization.

Avraham Shinnar, Jérôme Siméon, and Martin Hirzel. In ECOOP 2015.

http://hirzels.com/martin/papers/ecoop15-rules-nra.pdf

Horn Clauses as an Intermediate Representation for Program Analysis and Transformation

Graeme Gange, Jorge A Navas, Peter Schachte, Harald Sondergaard and Peter J. Stuckey. In ICLP 2015.

http://www.clip.dia.fi.upm.es/~jorge/docs/lpvm.pdf

Advanced processing for ontological queries,

Andrea Calì, Georg Gottlob, Andreas Pieris,

VLDB, 2010.

http://www.vldbarc.org/pvldb/vldb2010/papers/R49.pdf

Description logic rules,

Markus Krötzsch, Sebastian Rudolph, Pascal Hitzler,

ECAI 2008.

http://corescholar.libraries.wright.edu/cgi/viewcontent.cgi?article=1139&context=cse

Heuristics Entwined with Handlers Combined.

Tom Schrijvers and Nicolas Wu and Benoit Desouter and Bart Demoen.

In PPDP 2014.

http://people.cs.kuleuven.be/~tom.schrijvers/Research/papers/ppdp2014.pdf

Abstract rewriting approach to solve Datalog programs.

Fernando Tarin Morales, Fuyuki Isihikawa, Shinichi Honiden. DBLP 2015.

http://dl.acm.org/ft_gateway.cfm?id=2815076&ftid=1636453&dwn=1&CFID=832842527&CFTOKEN=73347840

Schedule

9/1 Organizational meeting. AND Saksham will present "Modern SAT, QBF, and CSP solvers : Algorithms and Techniques"

9/8 Priya will present "aspartame: Solving Constraint Satisfaction Problems with Answer Set Programming" by Mutsunori Banbara, Martin Gebser, Katsumi Inoue, Max Ostrowski, Andrea Peano, Torsten Schaub, Takehide Soh, Naoyuki Tamura and Matthias Weise.

In Proceedings of Answer Set Programming and Other Computing Paradigms (ASPOCP 2013), 6th International Workshop, August 25, 2013, Istanbul, Turkey.

http://www.cs.uni-potsdam.de/wv/pdfformat/bageinospescsotawe15a.pdf

9/15 Venkateswara will present "Rewriting recursive aggregates in answer set programming: back to monotonicity" by Mario Alviano, Wolfgang Faber and Martin Gebser. In ICLP 2015.

http://arxiv.org/pdf/1507.03923v1.pdf

9/22 Sen will present "Inference in the FO(C) Modelling Language" by Bart Bogaerts, Joost Vennekens, Marc Denecker, and Jan Van den Bussche. In ECAI 2014.

http://arxiv.org/pdf/1404.6368v1.pdf

9/29 Manaswi will present "Yedalog: Exploring Knowledge at Scale". Brian Chin, Daniel von Dincklage, Vuk Ercegovac, Peter Hawkins, Mark S. Miller, Franz Och, Chris Olston, Fernando Pereira. 1st Summit on Advances in Programming Languages (SNAPL 2015).

http://static.googleusercontent.com/media/research.google.com/en//pubs/archive/43462.pdf

10/6 Tiantian wil present his ICLP paper: http://arxiv.org/abs/1608.01338

10/13 Sarthak Ghosh will have his RPE:

Title: Value of Information in Probabilistic Reasoning

Decision making based on probabilistic reasoning typically involves selecting a subset of several expensive observations that best predict the system state. In a medical expert system, for example, we have to choose among several expensive diagnostic tests to become most certain about a patient's condition while minimizing costs as well as the negative impacts on their health. Again, in active sensing tasks, the goal is to choose the subset of sensors that is expected to provide the greatest reduction in uncertainty associated with a system, while limiting energy expenditure. The contribution of an observation to the overall utility of the system is referred to as its Value of Information (VoI). The observations may be chosen a priori in an open-loop fashion, or sequentially one after another as a closed-loop plan.

Starting with decision trees, a sizable portion of work have explored myopic/greedy approaches for solving the VoI problem. Unfortunately, in addition to myopic strategies not being sufficient for solving the problems optimally, they offer no performance guarantees. Also, non-myopically optimizing the VoI even in polytree graphical models has been shown to be NP^PP-complete. However, in case of chain-structured graphical models, such as Hidden Markov Models (HMMs), the VoI can be non-myopically optimized in polynomial-time.

In this work, we briefly review the diverse array of myopic and non-myopic approaches that have been used to tackle the VoI problem. We also present a new technique based on the MDP-framework that computes the VoI for arbitrary Dynamic Bayesian Networks (DBNs) in polynomial time with performance guarantees.

10/20 Cancelled (many of us are at ICLP2016 in New York: http://software.imdea.org/Conferences/ICLP2016/ ).

10/27 Tuncay.

11/3 Kumar will present "Inference and learning in probabilistic logic programs using weighted Boolean formulas" by Fierens, Daan, Van den Broeck, Guy, Renkens, Joris, Shterionov, Dimitar, Gutmann, Bernd, Thon, Ingo, Janssens, Gerda, De Raedt, Luc. In Theory and Practice of Logic Programming, 15 (3): 358-401, 2015

https://lirias.kuleuven.be/handle/123456789/392821

11/ 10 Arnab will present "The complexity of theorem-proving procedures". Cook SA. In Proceedings of the third annual ACM symposium on Theory of computing 1971 May 3 (pp. 151-158). ACM.

http://www.chell.co.uk/media/product/_master/1/files/cook_complexity_of_theorem_proving_procedures_19712.pdf

11/17 Chris will present "Computing most probable worlds of action probabilistic logic programs: scalable estimation for 10^30,000 worlds" by Samir Khuller, M Vanina Martinez, Dana Nau, Amy Sliva, Gerardo I Simari, Venkatramanan Siva Subrahmanian, Annals of Mathematics and Artificial Intelligence, 2007.

http://www.ccs.neu.edu/home/asliva/papers/somaMPW-amai07.pdf

11/25 Thanksgiving break

12/1 Saksham will present "FAQ: Questions asked Frequently" by Mahmoud Abo Khamis, Hung Q. Ngo, Atri Rudra (LogicBlox), PODS 2016.

http://arxiv.org/abs/1504.04044

12/8 Ashkan will present A logic for strategic reasoning. Wiebe van der Hoek, Wojciech Jamroga, Michael Wooldridge.

AAMAS '05 Proceedings of the fourth international joint conference on Autonomous agents and multiagent systems.

http://www.cs.huji.ac.il/course/2005/aisemin/articles2006/docs/pa1d4_157.pdf

----------------------------------

Formalizing Negotiations Using Logic Programming.

Mahmoud Abo Khamis, Hung Q. Ngo, Atri Rudra (LogicBlox).

FAQ: Questions asked Frequently. PODS 2016. (2016)

http://arxiv.org/abs/1504.04044

Abstract rewriting approach to solve Datalog programs.

Fernando Tarin Morales, Fuyuki Isihikawa, Shinichi Honiden. DBLP 2015. (2015)

http://dl.acm.org/ft_gateway.cfm?id=2815076&ftid=1636453&dwn=1&CFID=832842527&CFTOKEN=73347840

Inference and learning in probabilistic logic programs using weighted Boolean formulas.

Fierens, Daan, Van den Broeck, Guy, Renkens, Joris, Shterionov, Dimitar, Gutmann, Bernd, Thon, Ingo, Janssens, Gerda, De Raedt, Luc.

In Theory and Practice of Logic Programming, 15 (3): 358-401. (2015)

https://lirias.kuleuven.be/handle/123456789/392821

aspartame: Solving Constraint Satisfaction Problems with Answer Set Programming

Mutsunori Banbara, Martin Gebser, Katsumi Inoue, Max Ostrowski, Andrea Peano, Torsten Schaub, Takehide Soh, Naoyuki Tamura and Matthias Weise.

In Proceedings of Answer Set Programming and Other Computing Paradigms (ASPOCP 2013), 6th International Workshop, August 25, 2013, Istanbul, Turkey. (2013)

http://www.cs.uni-potsdam.de/wv/pdfformat/bageinospescsotawe15a.pdf

Rewriting recursive aggregates in answer set programming: back to monotonicity

Mario Alviano, Wolfgang Faber and Martin Gebser. In ICLP 2015. (2015)

http://arxiv.org/pdf/1507.03923v1.pdf

Complexity and Compilation of GZ-Aggregates in Answer Set Programming

Mario Alviano and Nicola Leone. In ICLP 2015. (2015)

http://arxiv.org/pdf/1507.03922v1.pdf

Inference in the FO(C) Modelling Language.

Bart Bogaerts, Joost Vennekens, Marc Denecker, and Jan Van den Bussche.

In ECAI 2014. (2014)

http://arxiv.org/pdf/1404.6368v1.pdf

Constraint Propagation for First-Order Logic and Inductive Definitions,