Main Program – Week 2

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
Executable Semantic Parsing (A)
J. Berant | C2.06
Algebraic Specification and Verification (I)
K. Futatsugi & N. Preining | A5.18 (*)
Formal Semantics of Natural Language (F)
Y. Winter | D1.02
Modeling Dialogue: Building Highly Responsive Conversational Agents (A)
S. Kopp & D. Schlangen | C3.06 (*)
Algorithmic Aspects of WQO Theory (A)
S. Schmitz & P. Schnoebelen | D1.01
Composition in Probabilistic Language Understanding (A)
G. Scontras | D1.03
Coffee Break
Linguistic Datasets
C. Biemann | C3.06
Introduction to Non-monotonic Logic (I)
C. Beirlaen & C. Straßer | D1.03
A Journey through the Possible Worlds of Modal Logic (F)
V. Goranko | D1.01
Referential Semantics One Step Further (W)
L. McNally & C. Umbach | C2.06
Computational Semantics (I)
J. Bos | D1.02
Logics on Words and Trees with Data (A)
D. Figueira & R. Lazic | C2.01
Natural Language Processing of Microblogs (I)
T. Scheffler & M. Stede | D1.03
Logical Foundations of Databases (F)
D. Figueira & G. Puppis | D1.01 (*)
Quotation (I)
E. Maier | C2.01
Introduction to Combinatory Categorial Grammar (I)
M. Steedman | D1.02
Mean Payoff Games, Max-Atoms, and Constraint (A)
M. Mamino | C3.06
Deontic Modality: Linguistic and Logical Perspectives on Oughts and Ends (A)
C. Condoravdi & L. van der Torre | C2.06 (*)
Coffee Break
Student Session | D1.01
Learning from Data: A Foundational Course for Linguistics (F)
M. Nissim | D1.02
An Introduction to Probabilistic Abstract Interpretation (I)
A. Di Pierro & H. Wiklicky | C3.06
Genericity in Natural Language (I)
G. Katz & R. Zamparelli | C2.06
5th International Workshop on Formal Approaches to Particles (W)
G. van Bergen, L. Hogeweg & H. Zeevat | D1.01
Query Answering with Description Logic Ontologies (A)
M. Bienvenu & M. Ortiz | C2.01
The Role of Linguistic Interpretation in Human Failures of Reasoning (I)
S. Mascarenhas | D1.03

(*) The lecture room has been changed with respect to the one reported in the booklet.

Main Program – Week 1

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
Foundations of Graph Transformation and Graph Grammars (F)
F. Drewes | C2.06 (*)
Description Logics: A Nice Family of Logics (F)
U. Sattler & T. Schneider | D1.03
Countability in the Nominal and Verbal Domains (A)
H. Filip & P. Sutton | C3.06
Computational Historical Linguistics (A)
G. Jäger | D1.02 (*)
Models of Bounded Rationality (A)
T. Icard | C2.01
Displacement Logic for Grammar (A)
G. Morrill & O. Valentin | D1.01
Coffee Break
Sentence Comprehension as a Cognitive Process: A Computational Approach (F)
F. Engelmann & S. Vasishth | D1.02
The Distributed Ontology, Modeling and Specification
Language DOL
O. Kutz & T. Mossakowski | D1.01
Corpus Methods for Research in Pragmatics (I)
J. Degen | C2.01
Computational Models of Events (A)
J. Pustejovsky
Model Counting for Logical Theories (I)
D. Chistikov & R. Dimitrova | C2.06
Modal Indefinites (A)
P. Melendez-Benito | C3.06
Distributional Semantics – A Practical Introduction (I)
S. Evert | D1.02
A Logical Approach to Isomorphism Testing and Constraint Satisfaction (A)
O. Verbitsky | C2.06 (*)
Logics and Natural Language Semantics
P. Egré & B. Spector | D1.01 (*)
Speech and Language Processing for Interactive Systems
T. Baumann & A. Köhn | C3.06
Social Choice Theory for Logicians (A)
E. Pacuit | C2.01 (*)
An Introduction to Dependent Type Semantics (A)
D. Bekki & K. Mineshima | D1.03 (*)
Coffee Break
Student Session | D1.01
Grammar Engineering
D. Flickinger & S. Oepen | A5.18
Type Theory. A Constructive Foundation for Logics and Computer Science (I)
A. Abel | C2.01
of Reasoning: Logic and Cognition
J. Szymanik | D1.03
DSALT: Distributional Semantics and Linguistic Theory (W)
G. Boleda & D. Paperno | D1.02
Improving Language Technology with Fortuitous Data (A)
Z. Agic, A. Johannsen & B. Plank | D1.01
Logics of Agency (I)
N. Troquard | C3.06

(*) The lecture room has been changed with respect to the one reported in the booklet.

Formal, Probabilistic and Typological Approaches to Discourse Particles and Modal Adverbs

Henk Zeevat, Lotte Hogeweg, and Geertje van Bergen


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 non-truth-conditional 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.



Day Time Authors and Title
Mo (22-8) 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 Osa-Gomez: Discourse particles and asymmetries in knowledge: the case of two Spanish discourse markers
Tue (23-8) 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 even-like and for only-like particles: Evidence from Modern Hebrew
Wed (24-8) 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 (25-8) 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 (26-8) 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 conditional-interrogative link


Invited Speaker

Lisa Matthewson


Henk Zeevat (chair)
Lotte Hogeweg
Geertje van Bergen

Programme Committee

Geertje van Bergen
Liz Coppock
Lisa Matthewson
Henk Zeevat
Lotte Hogeweg (chair)Hans-Christian Schmitz
Elena Karagjosova
Andrej Malchukov
Barbara Tomasciewicz
Katja Jasinskaja
Sebastian Loebner
Regine Eckhardt



Organisational questions pertaining to the workshop can be asked to Henk Zeevat (, questions about the programme to Lotte Hogeweg ( and practical ones to the ESSLLI organisation (

Referential Semantics One Step Further:
Incorporating Insights from Conceptual and Distributional Approaches to Meaning

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
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 prefix-verbs(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 Wrap-up


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 conceptually-oriented 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 cognitively-informed 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 3-way 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


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

Query Answering with Description Logic Ontologies

Meghyn Bienvenu and Magdalena Ortiz

  • Area: LoCo
  • Level: A
  • Week: 2
  • Time: 17:00 – 18:30
  • Room: C2.01


Recent years have seen an increasing interest in ontology-mediated 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 ontology-mediated 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.



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: Ontology-Based Data Access with Ontop

Additional References

Mean Payoff Games, Max-Atoms, and Constraint Satisfaction Problems

Marcello Mamino

  • Area: LoCo
  • Level: A
  • Week: 2
  • Time: 14:00 – 15:30
  • Room: C3.06


This course is intended to expose the audience to the following topics,
from a computational point of view: mean payoff games, max-plus 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
inter-domain relations which have been the subject of recent research.


Additional References

Logics on Words and Trees with Data

Diego Figueira and Ranko Lazić

  • Area: LoCo
  • Level: A
  • Week: 2
  • Time: 11:00 – 12:30
  • Room: C2.01


This course will present several results linking logics for semistructured data (such as XML) with counter systems. The course will focus on two well-studied 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 semi-structured 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: first-order logics, temporal logics, and path logics.

The course material should be useful to anyone with an interest in query languages for semi-structured data, counter systems or more generally on verification of infinite-state systems. This course has some technically demanding parts, and should appeal mainly to an audience from Logic, Verification and Theoretical Computer Science.



  • Words and trees with data
  • Overview of reasoning formalisms
  • Automata with counters, decidable and undecidable problems


  • First-order logic with 2 variables
  • Linear temporal logic with the freeze quantifier
  • Class-memory automata, alternating register automata
  • Connections to automata with counters
  • Infinite data words

Additional References

Algorithmic Aspects of WQO Theory

Sylvain Schmitz and Philippe Schnoebelen

  • Area: LoCo
  • Level: A
  • Week: 2
  • Time: 09:00 – 10:30
  • Room: D1.01


Well-quasi-orderings (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 Robertson-Seymour Theorem (for graphs and their minors). What is not very well known is that wqo-based 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 well-structured 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

  1. well-quasi-orders (wqos): examples and characterisations
  2. applications of wqos: well-structured transition systems (WSTS), termination proofs, relevance logic
  3. complexity: fast-growing complexity, Hardy computations, length function theorems
  4. ideals: effective representations and algorithmics
  5. applications of ideals: complete WSTS, coverability algorithms


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.
  • Figueira, D., 2012. Alternating register automata on finite words and trees. Logical Methods in Computer Science, 8(1):22. doi:10.2168/LMCS-8(1:22)2012.
  • Finkel, A. and Schnoebelen, Ph., 2001. Well-structured transition systems everywhere!
    Theoretical Computer Science, 256(1–2):63–92. doi:10.1016/S0304-3975(00)00102-X.
  • 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.
  • Milner, E.C., 1985. Basic WQO- and BQO-theory. 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/978-94-009-5315-4_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. Multiply-recursive upper bounds with Higman’s Lemma. In ICALP 2011, volume 6756 of Lecture Notes in Computer Science, pages 441–452. Springer. doi:10.1007/978-3-642-22012-8_35.
  • Schnoebelen, Ph., 2010a. Revisiting Ackermann-hardness 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/978-3-642-15155-2_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/978-3-662-47666-6_35.

Logical Foundations of Databases

Diego Figueira and Gabriele Puppis

  • Area: LoCo
  • Level: F
  • Week: 2
  • Time: 14:00 – 15:30
  • Room: D1.01


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 first-order 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
    1. First-order logic
    2. Relational Algebra
  • Day 2. Evaluation and satisfiability
    1. Data complexity, combined complexity
    2. Complexity of model checking
    3. Undecidability of satisfiability problem
  • Day 3. Conjunctive Queries (CQ)
    1. CQ = Select-Project-Join fragment of Relational Algebra
    2. CQ = Existential-Positive FO (EPFO)
    3. Duality of CQ’s and structures
    4. Chandra-Merlin Lemma
  • Day 4. Complexity of problems on CQ
    1. Evaluation problem
    2. Containment and equivalence problems
    3. Evaluation problem for bounded-width CQ
  • Day 5. Expressiveness of FO
    1. Ehrenfeucht-Fraïssé games
    2. Hanf and Gaiffman locality
    3. 0-1 Law


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

[2] Leonid Libkin. Finite Model Theory. Springer, 2004.

An Introduction to Probabilistic Abstract Interpretation

Alessandra Di Pierro and Herbert Wiklicky

  • Area: LoCo
  • Level: I
  • Week: 2
  • Time: 17:00 – 18:30
  • Room: C3.06


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 pseudo-inverse 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).





Additional References