QuantLA

Quantitative Logics and Automata

Research group

People

Information
Publications

Contact Franz Baader
http://lat.inf.tu-dresden.de/quantla/
2012 – 2022
funded by DFG

Both automata and logics are employed as modelling approaches in Computer Science, and these approaches often complement each other in a synergetic way. In Theoretical Computer Science the connection between finite automata and logics has been investigated in detail since the early nineteen sixties. This connection is highly relevant for numerous application domains. Examples are the design of combinatorial and sequential circuits, verification, controller synthesis, knowledge representation, natural language processing, or the design of XML technology. Classical logics and automata models support modelling of qualitative properties. For many Computer Science applications, however, such purely functional models are not sufficient since also quantitative phenomena need to be modelled. Examples are the vagueness and uncertainty of a statement, length of time periods, spatial information, and resource consumption. For this reason, different kinds of quantitative logics and automata models have been introduced. However, their connection is not as well-investigated as in the classical qualitative case.

The aim of this research training group is to investigate quantitative logics and automata as well as their connection in a thorough and complete manner, using methods from Theoretical Computer Science. As possible applications we consider problems from verification, knowledge representation, and processing of tree-structured data.

The planned qualification and supervision concept aims at providing the doctoral students with as much freedom as possible for their research work, while optimally preparing them for and supporting them in their research activities. The curriculum consists — in addition to the weekly research seminar — of Reading Groups, a Summer School in the first year of every cohort, advanced lectures, and an annual workshop. In addition, the doctoral students will participate in softskills courses offered by the participating universities.

Journal Articles

Shima Asaadi, Eugenie Giesbrecht, Sebastian Rudolph
Compositional matrix-space models of language: Definitions, properties, and learning methods
Natural Language Engineering, 29(1):1-49, January 2023
Details Download

Luisa Herrmann
Linear weighted tree automata with storage and inverse linear tree homomorphisms
Information and Computation, 281, 2021
Details

Luisa Herrmann, Heiko Vogler, Manfred Droste
Weighted automata with storage
Information and Computation, 269, 2019
Details

Johannes Osterholzer, Toni Dietze, Luisa Herrmann
Linear context-free tree languages and inverse homomorphisms
Information and Computation, 269, 2019
Details

Zoltán Fülöp, Luisa Herrmann, Heiko Vogler
Weighted Regular Tree Grammars with Storage
Discrete Mathematics & Theoretical Computer Science, 20(1), 2018
Details

Claudia Carapelle, Alexander Kartzow, Markus Lohrey
Satisfiability of ECTL* with Constraints
Journal of Computer and System Sciences, 82(5):826 - 855, 2016
Details

Daniel Borchmann, Rafael Peñaloza, Wenqian Wang
Classifying Software Bug Reports Using Methods from Formal Concept Analysis
Studia Universitatis Babeş-Bolyai Informatica, 59:10-27, June 2014
Details Download

Uwe Ryssel, Felix Distel, Daniel Borchmann
Fast algorithms for implication bases and attribute exploration using proper premises
Annals of Mathematics and Artificial Intelligence, Special Issue 65:1-29, 2013
Details Download

Proceedings Articles

Manuel Bodirsky, Thomas Feller, Simon Knäuer, Sebastian Rudolph
On Logics and Homomorphism Closure
Proceedings of the 36th Annual Symposium on Logic in Computer Science (LICS 2021), 1-13, 2021. IEEE
Details Download

Christel Baier, Martin Diller, Clemens Dubslaff, Sarah Alice Gaggl, Holger Hermanns, Nikolai Käfer
Admissibility in Probabilistic Argumentation
In Meghyn Bienvenu, Gerhard Lakemeyer, Esra Erdem, eds., Proceedings of the 18th International Conference on Principles of Knowledge Representation and Reasoning (KR 2021), 87-98, November 2021
Details Download

Frederic Dörband, Thomas Feller, Kevin Stier
Approximated Determinisation of Weighted Tree Automata
In Alberto Leporati, Carlos Martín-Vide, Dana Shapira, Claudio Zandron, eds., Language and Automata Theory and Applications. LATA 2021., volume 12638 of Lecture Notes in Computer Science, 255-266, February 2021. Springer
Details Download

Frederic Dörband, Thomas Feller, Kevin Stier
Sequentiality of Group-Weighted Tree Automata
In Alberto Leporati, Carlos Martín-Vide, Dana Shapira, Claudio Zandron, eds., Language and Automata Theory and Applications. LATA 2021., volume 12638 of Lecture Notes in Computer Science, 267-278, February 2021. Springer
Details Download

Franz Baader, Filippo De Bortoli
Description Logics That Count, and What They Can and Cannot Count
In Laura Kovacs, Konstantin Korovin, Giles Reger, eds., ANDREI-60. Automated New-era Deductive Reasoning Event in Iberia, volume 68 of EPiC Series in Computing, 1-25, 2020. EasyChair
Details

Franz Baader, Filippo De Bortoli
Description Logics that Count, and What They Can and Cannot Count (Extended Abstract)
In Stefan Borgwardt, Thomas Meyer, eds., Proceedings of the 33rd International Workshop on Description Logics (DL'20), volume 2663 of CEUR Workshop Proceedings, 2020. CEUR-WS
Details

Sebastian Rudolph, Lukas Schweizer, Zhihao Yao
SPARQL Queries over Ontologies Under the Fixed-Domain Semantics
In Abhaya C. Nayak, Alok Sharma, eds., PRICAI 2019: Trends in Artificial Intelligence - 16th Pacific Rim International Conference on Artificial Intelligence, Cuvu, Yanuca Island, Fiji, August 26-30, 2019, Proceedings, Part I, volume 11670 of Lecture Notes in Computer Science, 486--499, August 2019. Springer
Details Download

Franz Baader, Filippo De Bortoli
On the Expressive Power of Description Logics with Cardinality Constraints on Finite and Infinite Sets
In Andreas Herzig, Andrei Popescu, eds., Proc. of the 12th International Symposium on Frontiers of Combining Systems (FroCoS 2019), volume 11715 of Lecture Notes in Computer Science, 203-219, 2019. Springer
Details

Christian Al-Rabaa, Lukas Schweizer, Sebastian Rudolph
Faceted Answer-Set Navigation
In Christoph Benzmüller, Francesco Ricca, Xavier Parent, Dumitru Roman, eds., Rules and Reasoning - Second International Joint Conference, RuleML+RR2018, Luxembourg, September 18-21, 2018, Proceedings, volume 11092 of Lecture Notes in Computer Science, 211--225, September 2018. Springer
Details Download

Sebastian Rudolph, Lukas Schweizer, Satyadharma Tirtarasa
Justifications for the Description Logics Knowledge Bases under the Fixed-Domain Semantics
In Christoph Benzmüller, Francesco Ricca, Xavier Parent, Dumitru Roman, eds., Rules and Reasoning - Second International Joint Conference, RuleML+RR2018, Luxembourg, September 18-21, 2018, Proceedings, volume 11092 of Lecture Notes in Computer Science, 185--200, September 2018. Springer
Details Download

Luisa Herrmann
A Medvedev Characterization of Recognizable Tree Series
In Émilie Charlier, Julien Leroy, Michel Rigo, eds., Developments in Language Theory, volume 10396 of Lecture Notes in Computer Science, 210-221, 2017. Springer
Details

Sebastian Rudolph, Lukas Schweizer
Not too Big, Not too Small ... Complexities of Fixed-Domain Reasoning in First-Order and Description Logics
In Alessandro Artale, Birte Glimm and Roman Kontchakov, eds., Proceedings of the 30th International Workshop on Description Logics, volume 1879 of CEUR Workshop Proceedings, July 2017. CEUR-WS.org
Details Download

Sebastian Rudolph, Lukas Schweizer
Not too Big, Not too Small…Complexities of Fixed-Domain Reasoning in First-Order and Description Logics
In Oliveira Eugénio, Gama João, Vale Zita, Lopes Cardoso Henrique, eds., Progress in Artificial Intelligence: Proceedings of the 18th EPIA Conference on Artificial Intelligence, EPIA 2017, Porto, Portugal,, volume 10423 of Lecture Notes in Computer Science, 695-708, September 2017. Springer
Details

Shima Asaadi, Sebastian Rudolph
Gradual Learning of Matrix-Space Models of Language for Sentiment Analysis
In Phil Blunsom, Antoine Bordes, Kyunghyun Cho, Shay B. Cohen, Chris Dyer, Edward Grefenstette, Karl Moritz Hermann, Laura Rimell, Jason Weston, Scott Yih, eds., Proceedings of the 2nd Workshop on Representation Learning for NLP, ACL2017, 178-185, August 2017. Association for Computational Linguistics
Details Download

Sarah Alice Gaggl, Sebastian Rudolph, Lukas Schweizer
Fixed-Domain Reasoning for Description Logics
In Gal A. Kaminka, Maria Fox, Paolo Bouquet, Eyke Hüllermeier, Virginia Dignum, Frank Dignum, Frank van Harmelen, eds., Proceedings of the 22nd European Conference on Artificial Intelligence (ECAI 2016), volume 285 of Frontiers in Artificial Intelligence and Applications, 819 - 827, September 2016. IOS Press
Details Download

Franz Baader, Oliver Fernandez Gil
Extending the Description Logic tEL(deg) with acyclic TBoxes
Proceedings of the 22nd European Conference on Artificial Intelligence (ECAI 2016), to appear
Details

Luisa Herrmann, Heiko Vogler
Weighted Symbolic Automata with Data Storage
In Srečko Brlek, Christophe Reutenauer, eds., Developments in Language Theory, volume 9840 of Lecture Notes in Computer Science, 203-215, 2016. Springer
Details

Shima Asaadi, Sebastian Rudolph
On the Correspondence between Compositional Matrix-Space Models of Language and Weighted Automata
Proceedings of the ACL Workshop on Statistical Natural Language Processing and Weighted Automata (StatFSM 2016), August 2016
Details Download

Heiko Vogler, Manfred Droste, Luisa Herrmann
A Weighted MSO Logic with Storage Behaviour and Its Büchi-Elgot-Trakhtenbrot Theorem
In Adrian-Horia DediuJan Janoušek, Carlos Martín-Vide, Bianca Truthe, eds., Language and Automata Theory and Applications, volume 9618 of Lecture Notes in Computer Science, 127-139, 2016. Springer
Details

Johannes Osterholzer, Toni Dietze, Luisa Herrmann
Linear Context-Free Tree Languages and Inverse Homomorphisms
In Adrian-Horia DediuJan Janoušek, Carlos Martín-Vide, Bianca Truthe, eds., Language and Automata Theory and Applications, volume 9618 of Lecture Notes in Computer Science, 478-489, 2016. Springer
Details

Claudia Carapelle, Shiguang Feng, Alexander Kartzow, Markus Lohrey
Satisfiability of ECTL* with tree constraints
In D. Lev Beklemishev, V. Daniil Musatov, eds., Proceedings of Computer Science -- Theory and Applications: 10th International Computer Science Symposium in Russia (CSR 2015), 94 - 108, 2015. Springer International Publishing
Details

Claudia Carapelle, Shiguang Feng, Oliver Fernández Gil, Karin Quaas
Satisfiability for MTL and TPTL over non-monotonic data words
Language and Automata Theory and Applications: 8th International Conference, LATA 2014, 248--259, 2014. Springer International Publishing
Details

Claudia Carapelle, Shiguang Feng, Oliver Fernández Gil, Karin Quaas
On the expressiveness of MTL and TPTL over omega-data words
In Zoltán Ésik, Zoltán Fülöp, eds., Proceedings 14th International Conference on Automata and Formal Languages, volume 151, 174--187, 2014. Electronic Proceedings in Theoretical Computer Science
Details

Johannes Wollbold, Rüdiger Köhling, Daniel Borchmann
Attribute Exploration with Proper Premises and Incomplete Knowledge Applied to the Free Radical Theory of Ageing
In Cynthia Vera Glodeanu, Mehdi Kaytoue, Christian Sacarea, eds., Proceedings of the 12th International Conference on Formal Concept Analysis (ICFCA 2014), volume 8478 of Lecture Notes in Computer Science, 268-283, 2014. Springer
Details

Daniel Borchmann
Experience Based Nonmonotonic Reasoning
In Pedro Cabalar, Tran Cao Son, eds., Proceedings of the 12th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR 2013), volume 8148 of Lecture Notes in Computer Science, 200-205, 2013. Springer
Details Download

Claudia Carapelle, Alexander Kartzow, Markus Lohrey
Satisfiability of CTL* with Constraints
Proc. of the 24th Int. Conf. on Concurrency Theory (CONCUR 2013), 2013
Details

Daniel Borchmann
Axiomatizing EL^-Expressible Terminological Knowledge from Erroneous Data
Proceedings of the Seventh International Conference on Knowledge Capture, 1-8, 2013. ACM
Details Download

Doctoral Theses

Claudia Carapelle
On the Satisfiability of Temporal Logics with Concrete Domains
Phd thesis, Universität Leipzig, 2015/11/04
Details Download

Technical Reports

Manuel Bodirsky, Simon Knäuer, Sebastian Rudolph
Datalog-Expressibility for Monadic and Guarded Second-Order Logic
Technical Report, arXiv.org, volume 2010.05677, October 2020
Details Download

Franz Baader, Filippo De Bortoli
On the Complexity and Expressiveness of Description Logics with Counting
Technical Report, Chair of Automata Theory, Institute of Theoretical Computer Science, Technische Universität Dresden, volume LTCS-Report 19-09, December 2019
Details

Talks and Miscellaneous

Claudia Carapelle, Markus Lohrey
Temporal Logics with Local Constraints
Invited contribution. In Proceedings of the 24th EACSL Annual Conference on Computer Science Logic (CSL 2015), 2015
Details