The ninth edition of the QuantLA workshop is held as an online event from October 6 to October 8, 2021. Each session consists of several talks, given by current scholarship holders or students associated with the research training group, hosted on the Zoom platform. Credentials to access each session are provided via the internal mailing lists.


Program outline


Wednesday, October 6

13:00 - 13:15

Reception and announcements

13:15 - 14:15

TBD

Chair: Gustav Grabolle

TBD

14:15 - 14:30 Break

Session 1: Description Logics I

Chair: Lena Schiffer

14:30 - 15:15

Jakub Rydval

TBD

15:15 - 15:30 Break
15:30 - 16:15

Filippo De Bortoli

TBD

16:15 - 16:30 Break
16:30 - 17:00

Christian Alrabbaa

TBD

17:00 - 18:00 PI discussion

Thursday, October 7

Session 2: Weighted Automata I

Chair: Simon Knäuer

13:00 - 13:45

Gustav Grabolle

TBD

13:45 - 14:00 Break
14:00 - 14:45

Kevin Stier

TBD

14:45 - 15:00 Break

Session 3: Weighted Automata II + Markov Decision Processes

Chair: Jakub Rydval

15:00 - 15:45

Frederic Dörband

A general approach to determinisation of weighted automata

15:45 - 16:00 Break
16:00 - 16:30

Thomas Feller

TBD

16:30 - 17:00

Simon Jantsch

Witnessing subsystems for probabilistic systems with low tree width

17:00 - 18:00 PI discussion

Friday, October 8

Session 4: Combinatory Categorial Grammars + Description Logics II

Chair: Kevin Stier

13:00 - 13:45

Lena Schiffer

Parsing CCG with substitution rules and improved complexity

13:45 - 14:00 Break
14:00 - 14:45

Willi Hieke

TBD

14:45 - 15:00 Break

Session 5: Constraint Satisfaction Problems

Chair: Frederic Dörband

15:00 - 15:45

Simon Knäuer

Network satisfaction for symmetric relation algebras with a flexible atom

15:45 - 16:00 Break
16:00 - 16:30

Florian Starke

CSPs with finite duality closed under primitive positive constructions

16:30 - 17:00

Final remarks and farewell

17:00 - 18:00 PI discussion

 


Program


Wednesday, October 6

Session 1: Description Logics I

Filippo De Bortoli: title (TBD)

Abstract (TBD)

Jakub Rydval: title (TBD)

Abstract (TBD)

Christian Alrabbaa: title (TBD)

Abstract (TBD)

Thursday, October 7

Session 2: Weighted Automata I

Gustav Grabolle: title (TBD)

Abstract (TBD)

Kevin Stier: title (TBD)

Abstract (TBD)

Session 3: Weighted Automata II + Markov Decision Processes

Frederic Dörband: A general approach to determinisation of weighted automata

We introduce a general framework for determinisation of weighted automata (WA) over semirings which we call M-sequentialisation. The parameter M is a monoid and determines the granularity of the determinisation. Our framework includes classical determinisation, sequentialisation of automata using only a single operation, and crisp-determinisation. Moreover, we provide an M-sequentialisation construction which is applicable to a substantial class of WA, including finitely M-ambiguous WA and WA over idempotent semirings, with additional conditions on M. We show that every WA in this class is M-sequentialisable if it fulfills our notion of the twinning property.

Thomas Feller: title (TBD)

Abstract (TBD)

Simon Jantsch: Witnessing subsystems for probabilistic systems with low tree width

We consider the problem of computing minimal witnessing subsystems for Markov decision processes which have low path or tree width. Witnessing subsystems are subsystems which by themselves exceed a given threshold on the (maximal or minimal) probability of reaching some goal state. The corresponding decision problem is known to be NP-hard for acyclic Markov chains, but in P for Markov chains whose underlying graph is a tree. We show that the problem remains NP-hard for Markov chains with constant path width. As a second contribution, we describe an algorithm for the problem which uses a given tree partition of the MDP to compute a minimal witnessing subsystem. We show that it outperforms known approaches on some standard benchmarks which have a path like structure.

Friday, October 8

Session 5: Combinatory Categorial Grammars + Description Logics II

Lena Schiffer: Parsing CCG with substitution rules and improved complexity

We propose a new parsing algorithm for Combinatory Categorial Grammar (CCG), which is a formalism that is well-established in computational linguistics. CCG is mildly context-sensitive, so it is efficiently parsable and reaches an expressiveness that is conjectured to be suitable for modeling natural languages. We extend and improve the algorithm of Kuhlmann and Satta (2014) in three aspects. First, to our knowledge this is the first CCG parsing algorithm that can handle not only application and composition rules, but also substitution rules. Second, we not only give a recognition algorithm that returns a yes-or-no answer, but we describe the retrieval of the CCG derivation tree from the parse tree. Third, when regarding the grammar as part of the input, time complexity is exponential only in the maximum rule degree of the grammar, and not in the maximum length of lexical categories or lexical arguments. Our parsing algorithm therefore paves the way for a better understanding of the source of complexity of CCG parsing, which has previously been shown to be EXPTIME-complete (Kuhlmann, Satta, and Jonsson, 2018). This talk is based on joint work with Marco Kuhlmann and Giorgio Satta.

Willi Hieke: title (TBD)

Abstract (TBD)

Session 5: Constraint Satisfaction Problems

Simon Knäuer: Network satisfaction for symmetric relation algebras with a flexible atom

Robin Hirsch posed in 1996 the Really Big Complexity Problem: classify the computational complexity of the network satisfaction problem for all finite relation algebras A. We provide a complete classification for the case that A is symmetric and has a flexible atom; the problem is in this case NP-complete or in P. If a finite integral relation algebra has a flexible atom, then it has a normal representation 𝔅. We can then study the computational complexity of the network satisfaction problem of A using the universal-algebraic approach, via an analysis of the polymorphisms of 𝔅. We also use a Ramsey-type result of Nešetřil and Rödl and a complexity dichotomy result of Bulatov for conservative finite-domain constraint satisfaction problems.

Florian Starke: CSPs with finite duality closed under primitive positive constructions

Primitive positive constructions are a important tool to find reductions between CSPs. Rossmann showed in 2008 that a CSP is in AC0 if and only if its template has finite duality, i.e., a structure A has finite duality if there is a finite set of structures F such that the structures that have a homomorphism into A are precisely those into which no structure from F has a homomorphism. Our goal is to show that a CSP with template A can be primitively positively constructed from a finite structure with finite duality is if and only if A cannot primitively positively construct ({0,1},0,1,≤) or any directed cycle of length at least 2.