2016 Spring
Welcome to the homepage of CSE645 (Spring 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 Computer Science Department room 115.
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.
Combining Rewriting and Incremental Materialisation Maintenance for Datalog Programs with Equality
Boris Motik, Yavor Nenov, Robert Piro and Ian Horrocks
Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence (IJCAI 2015)
http://ijcai.org/papers15/Papers/IJCAI15-441.pdf
Incremental Update of Datalog Materialisation: the Backward/Forward Algorithm
Boris Motik, Yavor Nenov, Robert Edgar Felix Piro, Ian Horrocks
In AAAI 2015.
http://www.aaai.org/ocs/index.php/AAAI/AAAI15/paper/view/9660
Programming Tools with Big Data and Conditional Random Fields.
Veselin Raychev, Martin Vechev, Andreas Krause
POPL 2015.
http://www.srl.inf.ethz.ch/jsnice.php
Abstract rewriting approach to solve Datalog programs.
Fernando Tarin Morales, Fuyuki Isihikawa, Shinichi Honiden.
DBLP 2015.
http://2015.splashcon.org/event/dbpl2015-abstract-rewriting-approach-to-solve-datalog-programs
Solving puzzles described in English by automated translation to answer set programming and learning how to do that translation
Chitta Baral, Juraj Dzifcak
In AAAI Fall Symposium on Advances in Cognitive Systems 2011 (a revised but shorter version at KR 2012)
http://www.public.asu.edu/~cbaral/papers/puzzles11.pdf
Probabilistic Logic Programming Under the Distribution Semantics
Fabrizio Riguzzi, Terrance Swift, 2015.
File is attached at the end of the page.
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.
https://lirias.kuleuven.be/handle/123456789/392821
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.
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,
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
Planning as Tabled Logic Programming
Neng-Fa Zhou, Roman Bartak and Agostino Dovier. In ICLP 2015.
http://arxiv.org/pdf/1507.03979v1.pdf
A Formal Theory of Justifications,
Marc Denecker, Gerhard Brewka and Hannes Strass, LPNMR 2015.
http://www.informatik.uni-leipzig.de/~strass/2015/LPNMR15-16.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.
http://dl.acm.org/citation.cfm?doid=2499937.2499938
Tabling as a Library with Delimited Control.
Benoit Desouter, Marko van Dooren and Tom Schrijvers. In ICLP 2015.
http://arxiv.org/pdf/1507.08087v1.pdf
Parallel Execution of the ASP Computation - an Investigation on GPUs
Andrea Formisano, Flavio Vella, Agostino Dovier and Enrico Pontelli. In ICLP 2015.
http://ceur-ws.org/Vol-1068/paper-l11.pdf
Stable Models of Markov Logic Networks,
Joohyung Lee, Yunsong Meng and Yi Wang. In ICLP 2015.
http://www.aaai.org/ocs/index.php/SSS/SSS15/paper/viewFile/10277/10078
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
Probabilistic Preference Logic Networks.
Thomas Lukasiewicz, Maria Vanina Martinez, and Gerardo I. Simari.
In ECAI 2014.
http://www.cs.ox.ac.uk/people/gerardo.simari/personal/publications/PPLNs-ECAI2014-preprint.pdf
Ontological CP-Nets.
Tommaso Di Noia, Thomas Lukasiewicz, Maria Vanina Martinez, Gerardo I. Simari, Oana Tifrea-Marciuska.
In the Uncertainty Reasoning for the Semantic Web (URSW) workshop, held at the International Semantic Web Conferences (ISWC). 2014.
http://ceur-ws.org/Vol-900/pospaper1.pdf
Vicious Circle Principle and Logic Programs with Aggregates.
Michael Gelfond and Yuanlin Zhang.
In ICLP 2014.
http://arxiv.org/pdf/1405.3637v2.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
Sound Auction Specification and Implementation
http://dl.acm.org/citation.cfm?doid=2764468.2764511
Higher-Order Approximate Relational Refinement Types for Mechanism Design and Differential Privacy
http://arxiv.org/abs/1407.6845
Computer-aided Verification in Mechanism Design
http://arxiv.org/pdf/1502.04052.pdf
Schedule
1/28 Organizational meeting.
2/4 "The Many Uses of Rules in Ontology-Based Data Access" by Harold Boley, Faculty of Computer Science, University of New Brunswick, Canada.
Abstract: Ontology-Based Data Access (OBDA) enables automated reasoning over an ontology as a generalized global schema for the data in local (e.g., relational or graph) databases reachable through mappings. OBDA can semantically validate, enrich, and integrate heterogeneous data sources. Motivated by rule-ontology synergies, this talk discusses key concepts of OBDA and their foundation in three kinds of (logical) 'if-then' rules, using examples from the DeltaForest case study on the susceptibility of forests to climate change. (1) A query is a special Datalog rule whose conjunctive body can be rewritten (see 2) and unfolded (see 3), and whose n-ary head predicate instantiates the distinguished answer variables of the body predicates. OBDA ontologies beyond RDF Schema (RDFS) expressivity usually permit negative constraints for data validation, which are translated to Boolean conjunctive queries corresponding to integrity rules. (2) The OBDA ontology supports query rewriting and database materialization through global-schema-level reasoning. It usually includes the expressivity of RDFS, whose class and property subsumptions can be seen as single-premise Datalog rules with, respectively, unary and binary predicates, and whose remaining axioms are also definable by rules. OBDA ontologies often extend RDFS to the description logic DL-Lite (as in OWL 2 QL), including subsumption axioms that correspond to (head-)existential rules. Recent work has also explored Rule-Based Data Access (RBDA), e.g. via Description Logic Programs (as in OWL 2 RL, definable in RIF-Core), Datalog+/-, and Disjunctive Datalog. (3) OBDA data integration is centered on Global-As-View (GAV) mappings, which are safe Datalog rules allowing query unfolding of each global head predicate into a conjunction of local body predicates. These (heterogeneous) conjunctive queries can be further mapped to the database languages of the sources (e.g., to SQL or SPARQL). Conversely, the same GAV mappings allow database folding. The talk develops a unified architecture for (1) to (3).
Bio: Dr. Harold Boley is adjunct professor at the Faculty of Computer Science, University of New Brunswick, Canada, and chair of RuleML Inc. His work with international colleagues includes the specification of Web rules through the RuleML system of languages. The Deliberation RuleML family includes Datalog+/-, often used for Rule-Based Data Access. RuleML 1.02 is about to be released. RuleML has been combined with OWL to SWRL, has become the main input to the W3C Recommendation RIF, and has provided the foundation for OASIS LegalRuleML. His Rule Responder projects have enabled deployed distributed applications for the Social Semantic Web. His recent advances in data-plus-knowledge representation include the object-relational PSOA RuleML and the visualization framework Grailog. Harold (http://www.cs.unb.ca/~boley) is currently visiting the Department of Computer Science, Stony Brook.
2/11 Annie: Founded semantics of logic rules and its efficient computation
2/18 Akshit will present "Probabilistic Logic Programming Under the Distribution Semantics" by Fabrizio Riguzzi, Terrance Swift, 2015.
2/25 Caiwei will present "Incremental Update of Datalog Materialisation: the Backward/Forward Algorithm" by Boris Motik, Yavor Nenov, Robert Edgar Felix Piro, Ian Horrocks. In AAAI 2015.
http://www.aaai.org/ocs/index.php/AAAI/AAAI15/paper/view/9660
3/3 Sahil will present "Vicious Circle Principle and Logic Programs with Aggregates" by Michael Gelfond and Yuanlin Zhang. In ICLP 2014.
http://arxiv.org/pdf/1405.3637v2.pdf
3/10 Tiantian will present "asprin: Customizing Answer Set Preferences without a Headache" by Gerhard Brewka, James Delgrande, Javier Romero and Torsten Schaub. AAAI2015.
http://www.cs.uni-potsdam.de/wv/pdfformat/brderosc15a.pdf
3/17 Spring recess.
3/24 Harold Boley and Gen Zou: The Object-Relational PSOA RuleML and its PSOATransRun Realization
Abstract (Part 1): http://ruleml.org/talks/AWoSS2015/PSOARuleMLSQLSPARQL-AWoSS2015.pdf
Abstract (Part 2): http://ruleml.org/talks/AWoSS2015/PSOATransRun1.0-AWoSS2015.pdf
Slides (Part 1): http://www.cs.unb.ca/~boley/talks/PSOAObjRelDataRules-AWoSS2015-talk.pdf
Slides (Part 2): http://ruleml.org/talks/AWoSS2015/PSOATransRun1.0-AWoSS2015-talk.pdf
3/31 Shweta will present "Programming Tools with Big Data and Conditional Random Fields" by Veselin Raychev, Martin Vechev, Andreas Krause.
http://www.srl.inf.ethz.ch/jsnice.php
4/7 Yuxin will present "Solving puzzles described in English by automated translation to answer set programming and learning how to do that translation" by Chitta Baral, Juraj Dzifcak. In In AAAI Fall Symposium on Advances in Cognitive Systems 2011 (a revised but shorter version at KR 2012)
http://www.public.asu.edu/~cbaral/papers/puzzles11.pdf
4/14 Sumol will present "Planning as Tabled Logic Programming" by Neng-Fa Zhou, Roman Bartak and Agostino Dovier. In ICLP 2015.
http://arxiv.org/pdf/1507.03979v1.pdf
4/21 Chris will present "A Formal Theory of Justifications", Marc Denecker, Gerhard Brewka and Hannes Strass, LPNMR 2015.
http://www.informatik.uni-leipzig.de/~strass/2015/LPNMR15-16.pdf
4/28 Rajendra will present "Stable Models of Markov Logic Networks" by Joohyung Lee, Yunsong Meng and Yi Wang. In ICLP 2015.
http://www.aaai.org/ocs/index.php/SSS/SSS15/paper/viewFile/10277/10078
5/5 Neha will present "Tabling as a Library with Delimited Control" by Benoit Desouter, Marko van Dooren and Tom Schrijvers. In ICLP 2015.
http://arxiv.org/pdf/1507.08087v1.pdf
5/12 Delafrouz Mirfendereski will present: "The complexity of theorem-proving procedures" by Cook SA. In Proceedings of the third annual ACM symposium on Theory of computing 1971 May 3 (pp. 151-158). ACM.
5/19 Saksham will present "Sound Auction Specification and Implementation"
http://dl.acm.org/citation.cfm?doid=2764468.2764511