Each course and workshop spans a whole week (5 days). Participants are free to choose the courses they want to attend.
See also the main program of Week 1.
Each course belongs to one of the standard ESSLLI streams:
 LaCo = Language and Computation
 LaLo = Language and Logic
 LoCo = Logic and Computation
Each course corresponds to one of the following three levels:
 I = Introductory
 F = Foundational
 A = Advanced
(*) The lecture room has been changed with respect to the one reported in the booklet.
Each course and workshop spans a whole week (5 days). Participants are free to choose the courses they want to attend.
See also the main program of Week 2.
Each course belongs to one of the standard ESSLLI streams:
 LaCo = Language and Computation
 LaLo = Language and Logic
 LoCo = Logic and Computation
Each course corresponds to one of the following three levels:
 I = Introductory
 F = Foundational
 A = Advanced
(*) The lecture room has been changed with respect to the one reported in the booklet.
Henk Zeevat, Lotte Hogeweg, and Geertje van Bergen
Abstract
Discourse particles and modal adverbs form a borderline case between semantics and pragmatics and so can be the source of new insights in these areas. The use of particles has been connected with discourse relations and other coherence relations, the relation between semantic content and discourse context, especially the mutual knowledge and the common discourse goals of the discourse participants, with expression of speaker beliefs, desires and intentions and with the control of interpretations that go beyond semantic content, i.e. explicatures and implicatures. And, last but not least, particles and modal adverbs can contribute to expressive and other nontruthconditional aspects of meaning.
The workshop is the 5th in a series on formal approaches to particles and part of the ESSLLI summer school in Bolzano, taking place from 21 to 26 August 2016. The first of these took place in 2003 at a time where it was still an adventurous idea to apply formal methods to the elusive meanings of particles. The workshops however contributed to the serious progress that has been made in the area.
Program
Day 
Time 
Authors and Title 
Mo (228) 
17.00 – 17.30 
Geertje van Bergen, Lotte Hogeweg & Henk Zeevat: Introduction 
17.30 – 18.00 
Yael Greenberg: Interaction of a discourse particle with a metalinguistic operator: The case of x but X 
18.00 – 18.30 
Adriana OsaGomez: Discourse particles and asymmetries in knowledge: the case of two Spanish discourse markers 
Tue (238) 
17.00 – 17.30 
Mira Grubic: Additive particles, parallelity and distinctness 
17.30 – 18.00 
Katja Jasinskaja & Barbara Tomaszewicz: Dissociating the scalarity and additivity of EVEN – the case of ‘čak’ and ‘čak i’ in BCS 
18.00 – 18.30 
Yael Greenberg & Dina Orenstein: Typologies for evenlike and for onlylike particles: Evidence from Modern Hebrew 
Wed (248) 
17.00 – 18.00 
Lisa Matthewson: Towards a Landscape of Discourse Particles 
18.00 – 18.30 
Moria Ronen, Yael Greenberg & Galit Sassoon: A study of the Hebrew hedger ‘Begadol’ in exceptive sentences 
Thu (258) 
17.00 – 17.30 
Sophia Malamud & Allyson Ettinger: Utterance modifiers ‘ba’ and reverse‐polarity tags in the conversational scoreboard 
17.30 – 18.00 
Junwen Lee: A modal analysis of the Colloquial Singapore English particle ‘lah’ 
18.00 – 18.30 
Upsorn Tawilapakul: Discourse Particles of Thai and Their Prominent Features 
Fri (268) 
17.00 – 17.30 
Sonja Thoma: A systematic approach to DPRT function in Miesbach Bavarian 
17.30 – 18.00 
Anne Bertrand, Johannes Heim, Sonja Thoma & Martina Wiltschko: Let’s all be systematic (about confirmationals), eh?\

18.00 – 18.30 
Eva Csipak & Sarah Zobel: Discourse particles as a window into the conditionalinterrogative link 
Invited Speaker
Lisa Matthewson
Organizers
Henk Zeevat (chair)
Lotte Hogeweg
Geertje van Bergen
Programme Committee
Geertje van Bergen
Liz Coppock
Lisa Matthewson
Henk Zeevat
Lotte Hogeweg (chair)HansChristian Schmitz
Elena Karagjosova
Andrej Malchukov
Barbara Tomasciewicz
Katja Jasinskaja
Sebastian Loebner
Regine Eckhardt
Questions
Organisational questions pertaining to the workshop can be asked to Henk Zeevat (henk.zeevat@uva.nl), questions about the programme to Lotte Hogeweg (L.Hogeweg@uva.nl) and practical ones to the ESSLLI organisation (oc.esslli2016.unibz.it).
Louise McNally and Carla Umbach
 Workshop
 Week: 2
 Time: 11:00 – 12:30
 Room: C2.06
Workshop Program
Monday, 22.8 
11.00 – 11.15 
Louise McNally,
Carla Umbach 
Introduction 
11.20 – 11.40 
Alexandra Spalek (Oslo)
Barbara Tomaszwicz (Cologne) 
Coercion in Polish versus English: processing complex lexical content (slides) 
11.45 – 12.30 
Barbara Partee
(UMass Amherst) 
Lexical Semantics in Formal Semantics: History and Challenges (slides) 
Tuesday, 23.8 
11.00 – 11.30 
Staffan Larsson (Göteborg) 
Connecting Language, Perception and Interaction using Type Theory with Records(slides) 
11.35 – 12.20 
Alessandro Lenci (Pisa) 
“Going Dynamic” in Distributional Semantics(slides) 
12.20– 12.30 

Discussion: Distributional semantics 
Wednesday, 24.8 
11.00 – 11.20 
Matthew Gotham (Oslo) 
Conceptualization, Individuation and quantification(slides) 
11.25 – 11.55 
Stephanie Solt (ZAS Berlin) 
Degree and Quantity – Semantics and Conceptual Representation(slides) 
12.00 – 12.30 
Michael Glanzberg (Northwestern) 
The Cognitive Roots of Adjectival Meaning(slides) 
Thursday, 25.8 
11.00 – 11.30 
Antje Roßdeutscher, Tillmann Pross, Sebastian Pado, Gabriella Lapesa, Max Kisselew (Stuttgart) 
‘Over reference’: a comparative study on German prefixverbs(handout) 
11.35 – 12.20 
Marcus Kracht (Bielefeld) 
Simplicity of Meaning(slides) 
12.20– 12.30 

Discussion: Lexical semantics 
Friday, 26.8 
11.00 – 11.30 
Yoad Winter (Utrecht) 
A Role for Protoroles: Lexical Reciprocity and Logical Symmetry(slides) 
11.35 – 12.20 
Mark Steedman (Edinburgh) 
A Theory of Content(slides) 
12.20– 12.30 

Wrapup 
Contact
RefSemPlus2016@gmail.com
Workshop Description
Though referential approaches to semantics have proven very successful at providing meaningful analyses for a wide range of natural language data, some important phenomena, particularly involving the lexicon, have eluded insightful treatment. Notions going beyond reference and truth have been influencing referential semantics for years, but the interest in incorporating results and ideas from conceptuallyoriented semantics into referential approaches is noticeably increasing, as seen in the recent series of workshops devoted to the issue (see also e.g. Hamm et al. 2009, Carlson 2010). In parallel, interest has also grown in bringing related insights from cognitivelyinformed distributional models of meaning into formal semantics (Lenci 2008, Copestake & Herbelot 2012, Baroni et al. 2014).
The aim of this workshop is to promote a 3way dialog among these approaches in order to clarify natural points of contact and to generate specific hypotheses about how to improve the explanatory capacity of referential models in a principled and testable manner. We build from referential models given the empirical evidence that reference (whether to real or imaginary objects) is a fundamental part of linguistic communication. Crucially, however, reference makes use of complex descriptive content. Cognitive/conceptual approaches place greater emphasis precisely on the richness of descriptive content and richer theories of descriptive content clearly lead to richer accounts of compositional phenomena (see e.g. Kamp & Partee 1995, Zwarts & Winter 2000, Asher 2011, Del Pinal 2015, Gust & Umbach 2015, McNally, to appear). On the other hand, cognitive models are laborious to construct, difficult to implement/test, and face challenges in grounding. Compositional distributional models can help with the analysis of rich descriptive content but are not currently suited to dealing with reference. We therefore consider the incorporation of insights from conceptual and distributional models into referential approaches, rather than the reverse, the most viable strategy.
Invited Speakers
Barbara Partee, Marcus Kracht, Alessandro Lenci, Mark Steedman
Organizers
Louise McNally (Universitat Pompeu Fabra), Carla Umbach (ZAS Berlin / University of Cologne)
Scientific Committee
Guillermo Del Pinal, Marcus Kracht, Alessandro Lenci, Emar Maier, Louise McNally, Barbara Partee, Antje Rossdeutscher, Galit W. Sassoon, Martin Schäfer, Stephanie Solt, Mark Steedman, Carla Umbach
 Area: LoCo
 Level: A
 Week: 2
 Time: 17:00 – 18:30
 Room: C2.01
Abstract
Recent years have seen an increasing interest in ontologymediated query answering, in which the semantic knowledge provided by an ontology is exploited when querying data. Adding an ontology has several advantages (e.g. simplifying query formulation, integrating data from different sources, providing more complete answers to queries), but it also makes the query answering task more difficult. In this course, we give a introduction to ontologymediated query answering using description logic (DL) ontologies. Our focus is on DLs for which query answering scales polynomially in the size of the data, as these are best suited for applications requiring large amounts of data. We describe the challenges that arise when evaluating different natural types of queries in the presence of such ontologies, and we present algorithmic solutions based upon two key concepts: query rewriting and saturation. We conclude the course with an overview of recent results and active areas of ongoing research.
Although there are no formal prerequisites, some familiarity with description logics, knowledge representation and reasoning, and/or databases would be helpful. Students who are not already familiar with description logics are strongly encouraged to attend the foundational course “Description Logics: a Nice Family of Logics” offered during Week 1.
Slides
Handout
Unit 1: Introduction
Unit 2: Instance Queries
Unit 3: Conjunctive Queries
Unit 4: Navigational Queries
Unit 5: Queries with Negation and Other Forms of Recursion
Unit 6: Research Topics in OMQA
Unit 7: OntologyBased Data Access with Ontop
Additional References
Marcello Mamino
 Area: LoCo
 Level: A
 Week: 2
 Time: 14:00 – 15:30
 Room: C3.06
Abstract
This course is intended to expose the audience to the following topics,
from a computational point of view: mean payoff games, maxplus algebra,
constraint satisfaction problems. Each of the topics is vast, and would
easily require a course by itself, were all the major ramifications to be
presented. Our focus will be on presenting well known and hopefully
inspiring facts in each domain individually, and exposing a network of
interdomain relations which have been the subject of recent research.
Slides
Additional References
 Area: LoCo
 Level: A
 Week: 2
 Time: 11:00 – 12:30
 Room: C2.01
Abstract
This course will present several results linking logics for semistructured data (such as XML) with counter systems. The course will focus on two wellstudied data models: data words, and data trees. These are words and trees whose every element carries a label from a finite alphabet and a data value from an infinite domain; indeed these are standard abstractions for semistructured documents. The focus is on the complexity and decidability of reasoning on these structures. The plan is to show three groups of logics with very differing expressive power and capabilities, in order to give an overall idea of the state of the art and different powerful techniques for proving decidability in the area. These logics are divided into: firstorder logics, temporal logics, and path logics.
The course material should be useful to anyone with an interest in query languages for semistructured data, counter systems or more generally on verification of infinitestate systems. This course has some technically demanding parts, and should appeal mainly to an audience from Logic, Verification and Theoretical Computer Science.
Slides
Introduction:
 Words and trees with data
 Overview of reasoning formalisms
 Automata with counters, decidable and undecidable problems
Words:
 Firstorder logic with 2 variables
 Linear temporal logic with the freeze quantifier
 Classmemory automata, alternating register automata
 Connections to automata with counters
 Infinite data words
Additional References
 Area: LoCo
 Level: A
 Week: 2
 Time: 09:00 – 10:30
 Room: D1.01
Abstract
Wellquasiorderings (wqos) are a fundamental tool in logic and computer science. They provide termination arguments in a large number of decidability (or finiteness, regularity, …) results. In constraint solving, automated deduction, program analysis, and many more fields, wqos usually appear under the guise of specific tools, like Dickson’s Lemma (for tuples of integers), Higman’s Lemma (for words and their subwords), Kruskal’s Tree Theorem and its variants (for finite trees with embeddings), and recently the RobertsonSeymour Theorem (for graphs and their minors). What is not very well known is that wqobased proofs have an algorithmic content.
The purpose of this course is to provide an introduction to the algorithmic aspects of wqos: to present generic algorithms working on large classes of problems, to introduce the techniques used to prove complexity upper bounds and lower bounds, to explain the use of wqo ideals in algorithms, and provide several applications in logics (e.g. data logics, relevance logic), verification (prominently for wellstructured transition systems), and formal languages. Because wqos are in such wide use, we believe this topic to be of relevance to a broad community with interests in complexity theory and decision procedures for logical theories.
Planned Content
 wellquasiorders (wqos): examples and characterisations
 applications of wqos: wellstructured transition systems (WSTS), termination proofs, relevance logic
 complexity: fastgrowing complexity, Hardy computations, length function theorems
 ideals: effective representations and algorithmics
 applications of ideals: complete WSTS, coverability algorithms
Resources
Additional References
 Blondin, M., Finkel, A., and McKenzie, P., 2014. Handling infinitely branching WSTS.
In ICALP 2014, volume 8573 of Lecture Notes in Computer Science, pages 13–25.
doi:10.1007/9783662439517_2.
 Figueira, D., 2012. Alternating register automata on finite words and trees. Logical Methods in Computer Science, 8(1):22. doi:10.2168/LMCS8(1:22)2012.
 Finkel, A. and Schnoebelen, Ph., 2001. Wellstructured transition systems everywhere!
Theoretical Computer Science, 256(1–2):63–92. doi:10.1016/S03043975(00)00102X.
 Lazić, R. and Schmitz, S., 2015. The ideal view on Rackoff’s coverability technique. In
RP 2015, volume 9328 of Lecture Notes in Computer Science, pages 1–13. Springer.
doi:10.1007/9783319245379_8.
 Milner, E.C., 1985. Basic WQO and BQOtheory. In Rival, I., editor, Graphs and Order.
The Role of Graphs in the Theory of Ordered Sets and Its Applications, pages 487–502. doi:10.1007/9789400953154_14.
 Podelski, A. and Rybalchenko, A., 2004. Transition invariants. In LICS 2004, pages
32–41. IEEE. doi:10.1109/LICS.2004.1319598.
 Schmitz, S., 2016. Complexity hierarchies beyond Elementary. ACM Transactions on
Computation Theory, 8(1):1–36. doi:10.1145/2858784.
 Schmitz, S. and Schnoebelen, Ph., 2011. Multiplyrecursive upper bounds with Higman’s Lemma. In ICALP 2011, volume 6756 of Lecture Notes in Computer Science, pages 441–452. Springer. doi:10.1007/9783642220128_35.
 Schnoebelen, Ph., 2010a. Revisiting Ackermannhardness for lossy counter machines
and reset Petri nets. In MFCS 2010, volume 6281 of Lecture Notes in Computer Science, pages 616–628. Springer. doi:10.1007/9783642151552_54.
 Urquhart, A., 1999. The complexity of decision procedures in relevance logic II. Journal
of Symbolic Logic, 64(4):1774–1802. doi:10.2307/2586811.
 Wainer, S.S., 1972. Ordinal recursion, and a refinement of the extended Grzegorczyk
hierarchy. Journal of Symbolic Logic, 37(2):281–292. doi:10.2307/2272973.
 Weiermann, A., 1994. Complexity bounds for some finite forms of Kruskal’s Theorem.
Journal of Symbolic Computation, 18(5):463–488. doi:10.1006/jsco.1994.1059.
 Zetzsche, G., 2015. An approach to computing downward closures. In ICALP 2015,
volume 9135 of Lecture Notes in Computer Science, pages 440–451. Springer. doi:10.1007/9783662476666_35.
 Area: LoCo
 Level: F
 Week: 2
 Time: 14:00 – 15:30
 Room: D1.01
Abstract
The proposed course will present several fundamental results linking logics with database query languages. The course can thus serve as an introduction to finite model theory and database theory. More specifically, it will cover basic knowledge about firstorder logic, Relational Algebra and Conjunctive Queries; complexity of fundamental decision problems, such as evaluation and satisfiability; as well as results about expressiveness of specification languages. Regarding the logical formalisms, we will focus mainly on two important query languages for relational databases, namely, Relational Algebra and Conjunctive Queries. We will not assume any prior knowledge on either logic or databases, but some familiarity with basic results in complexity theory will be required. The goal of the course is to give the fundamental tools that enable a deeper understanding of database query languages.
Structure of the course and tentative schedule
The course will be given in English; however, if needed, questions can be posed and answered in French, Spanish, or Italian. The course will be structured into five lessons of about 90 minutes each.
Below is a tentative schedule of the covered subjects.
 Day 1. First Order logic (FO) basics
 Firstorder logic
 Relational Algebra
 Day 2. Evaluation and satisfiability
 Data complexity, combined complexity
 Complexity of model checking
 Undecidability of satisfiability problem
 Day 3. Conjunctive Queries (CQ)
 CQ = SelectProjectJoin fragment of Relational Algebra
 CQ = ExistentialPositive FO (EPFO)
 Duality of CQ’s and structures
 ChandraMerlin Lemma
 Day 4. Complexity of problems on CQ
 Evaluation problem
 Containment and equivalence problems
 Evaluation problem for boundedwidth CQ
 Day 5. Expressiveness of FO
 EhrenfeuchtFraïssé games
 Hanf and Gaiffman locality
 01 Law
Slides
Day 1
Day 2
Day 3
Day 4
Day 5
Additional References
[1] Serge Abiteboul, Richard Hull, Victor Vianu, Foundations of Databases. Addison Wesley.
Available online at http://webdam.inria.fr/Alice/
[2] Leonid Libkin. Finite Model Theory. Springer, 2004.
Alessandra Di Pierro and Herbert Wiklicky
 Area: LoCo
 Level: I
 Week: 2
 Time: 17:00 – 18:30
 Room: C3.06
Abstract
This introductory course will be concerned with the probabilistic analysis of deterministic and probabilistic programs, that is on how to obtain, estimate or approximate statistical or probabilistic judgements about certain (quantitative) properties of such programs.
In order to allow for a formal investigation of such features we will first discuss ways to specify or define the semantics of probabilistic programs; in particular to this purpose we will consider Discrete Time Markov Chains. Our focus will then be on Probabilistic Abstract Interpretation (PAI) as a way to obtain simplified or abstract versions of the concrete semantics of programs.
We will introduce the mathematical theory of PAI which is based on linear operators and a notion of pseudoinverse generalising the one of a Galois connection.
Various static and dynamic analysis techniques based on PAI will be demonstrated by presenting their applications, e.g. in the context of information security, and concrete calculations based on an experimental tool.
We will also discuss how this framework compares with other approaches towards probabilistic semantics (e.g. probabilistic traces and weakest preconditions) and program analysis (such as probabilistic model checking and verification).
Slides
Demo
Additional References