Department of Theoretical Computer Science
Members of our department are focused on
the more foundational aspects of Theoretical Computer Science and their
work can be classified into three main areas: Combinatorics,
Computational Complexity, and Mathematical Logic. In all these
areas, we strive not only to achieve new results but to broaden the
repertoire of approaches that are considered standard. In particular we
pursue three main aims:
Combinatorics: to study the
recent challenging problems of extremal graph theory and discrete random
structures, and thus contribute to these central topics in combinatorics
which are crucial e.g. for our understanding of very large networks.
Computational Complexity: to
deepen our knowledge of relations among complexity classes via standard
and non-standard computational models considering both the usual
complexity measures like time or space and new ones relevant in
neurocomputing and knowledge compilation.
Mathematical Logic: to
develop and apply non-classical logics for reasoning, in both natural
and artificial scenarios, with real-life information, which is often
uncertain, graded, or even contradictory, and changing over time.
Research Areas Combinatorics: Extremal Graph
Theory, Regularity Method, Probabilistic Method, Limits of Graphs,
Random Graphs, Discrete Structures, Computational Geometry,
Combinatorial and Algebraic Methods in Number Theory.
Computational Complexity:
Branching Programs, Neural Networks, Boolean Functions, Preprocessing
Instances for SAT Problem, Knowledge Compilation, Logical Descriptions
of Computation, Non-Standard Positional Numeral Systems.
Mathematical Logic :
Logic and Reasoning, Graded Notions, Vagueness, Uncertainty,
Mathematical Fuzzy Logic, Substructural Logics, Paraconsistent Logic,
Dynamic and Non-Monotonic Logic, Modal Logic, Abstract Algebraic Logic,
Complexity of Non-Classical Logics.
Work Groups and Their Seminars Combinatorial
group : Combinatorial group: a group dedicated to study of extremal graph
theory, discrete structures, graph limits, and computational geometry. We organize a
combinatorial
seminar .
LogICS : the group focuses on the study of (non-classical) logic. With
the Czech Society for Cybernetics and Informatics , we organize a seminar of applied mathematical logic (also called Hájek’s seminar
according to its founder), which has run continuously since the late
1960’s.
Transfinite Certificates of Convergence (2023-2025; GAČR)
Coalition and Epistemic Logic: An Intensional Approach to Groups (2022-2025; LA GAČR-DFG)
Graph limits and beyond (2021-2025; GAČR)
AppNeCo: Aproximate Neurocomputing (2022-2024; GAČR)
GRADLACT: Graded Logics of Action (2022-2024; GAČR)
Metamathematics of substructural modal logics (2022-2024; GAČR)
MOSAIC Modalities in Substructural Logics: Theory, Methods and
Applications (2021-2024; EU)
Random discrete structures (2020-2022, GAČR)
Supporting the internationalization of the Institute of Computer
Science of the Czech Academy of Sciences (2020-2022, MŠMT ČR)
Boolean Representation Languages Complete for Unit Propagation
(2019-2021; GAČR)
Embedding, Packing and Limits in Graphs (2019-2021; GAČR)
FoNeCo: Analytical Foundations of Neurocomputing (2019-2021;
GAČR)
National Competence Center – Cybernetics and Artificial
Intelligence (2019-2021; GAČR)
Structural properties of visibility in terrains and farthest color
Voronoi diagrams (2019-2021; GAČR)
Substructural Modal Logics for Knowledge Representation (2020-2021;
AV ČR)
CONNECT – Combinatorics of Networks and Computation (2017-2020;
H2020 MSCA RISE)
Enhancing human resources for research in theoretical computer
science (2018-2020; MŠMT)
Non-classical Logical Models of Information Dynamics (2018-2020;
GAČR)
Reasoning with Graded Properties (2018-2020; GAČR)
Predicate graded logics and their applications to computer science
2017-2019; GAČR)
SYSMICS: Syntax meets semantics: Methods, interactions, and
connections in substructural logics (2016-2019; GAČR)
Center of Excellence – Institute for Theoretical Computer Science
(2012-2018; GAČR)
Extremal graph theory and applications (2016-2018; GAČR)
Reasoning with Incomplete and Inconsistent Information (AV ČR,
2017)
Modelling vague quantifiers in mathematical fuzzy logic (2015-2017;
GAČR)
An Order-Based Approach to Non-Classical Propositional and
Predicate Logics (2013-2016; GAČR)
Algebraic Methods in Proof Theory (2011-2015; GAČR)
Distribution and metric properties of number sequences and their
applications (2012-2015; GAČR)
more
Selected Publications
Badia G.; Cintula Petr; Hájek Petr; Tedder Andrew . How Much Propositional Logic Suffices for Rosser’s Undecidability Theorem? Review of Symbolic Logic, 2022
Baltag Alexandru; Bezhanishvili Nick; Fernández-Duque David . The Topology of Surprise. KR 2022
Bílková Marta ; Frittella Sabine; Kozhemiachenko Daniil. Paraconsistent Gödel Modal Logic . IJCAR 2022Cintula Petr ; Grimau Berta; Noguera Carles; Smith Nicholas J. J. These degrees go to eleven: Fuzzy logics and gradable predicates . Synthese, 2022Doležal Martin; Grebík Jan; Hladký Jan ; Rocha Israel; Rozhoň Václav. Cut distance identifying graphon parameters over weak* limits . Journal of Combinatorial Theory, 2022
Gispert Joan; Haniková Zuzana ; Moraschini Tommaso; Stronkowski Michał. Structural Completeness in Many-Valued Logics with Rational Constants . Notre Dame Journal of Formal Logic, 2022
Šileikis Matas ; Warnke Lutz. Counting Extensions Revisited . Random Structures and Algorithms, 2022
Cintula Petr ; Noguera Carles. Logic and Implication: An Introduction
to the General Algebraic Study of Non-classical Logics . Springer, 2021Doležal Martin; Grebík Jan; Hladký Jan ; Rocha
Israel; Rozhoň Václav. Relating the cut distance and the weak* topology for
graphons . Journal of Combinatorial Theory, Series B, 2021
Jančar Petr; Šíma Jiří . The Simplest Non-Regular Deterministic
Context-Free Language . MFCS 2021
Klein Dominik; Majer Ondrej ; Rad Soroush Rafiee. Probabilities with
Gaps and Gluts . Journal of Philosophical Logic, 2021
Kučera P.; Savický Petr . Bounds on the
Size of PC and URC Formulas . Journal of Artificial Intelligence
Research, 2021
Sedlár Igor . Decidability and Complexity of Some Finitely-valued
Dynamic Logics . IJCAI 2021
Šíma Jiří; Žák Stanislav . A Polynomial-Time Construction of a Hitting Set for Read-once Branching Programs of Width 3 . Fundamenta Informaticae, 2021
Bose P.; Cano P.; Saumell Maria ; Silveira R.I. Hamiltonicity
for Convex Shape Delaunay and Gabriel Graphs . Computational
Geometry-Theory and Applications, 2020
Bílková Marta ; Colacito A. Proof Theory
for Positive Logic with Weak Negation . Studia Logica, 2020Moraschini Tommaso ; Wannenburg J. J. Epimorphism
Surjectivity in Varieties of Heyting Algebras . Annals of Pure and
Applied Logic, 2020Sedlár Igor; Tedder Andrew . Lambek
Calculus with Conjugates . Studia Logica, 2020Šíma Jiří . Analog Neuron
Hierarchy . Neural Networks, 2020Allen P.; Böttcher J.; Hladký Jan; Piguet
Diana . Packing degenerate graphs. Advances in Mathematics ,
2019
Cintula Petr ; Diaconescu D.; Metcalfe G. Skolemization
and Herbrand theorems for lattice-valued logics . Theoretical
Computer Science, 2019Moraschini Tommaso . On the
complexity of the Leibniz hierarchy . Annals of Pure and Applied
Logic, 2019Rozhoň Václav . A Local
Approach to the Erdős-Sós Conjecture . SIAM Journal on Discrete
Mathematics, 2019Šileikis Matas ; Warnke L. A
counterexample to the DeMarco-Kahn Upper Tail Conjecture . Random
Structures and Algorithms, 2019Kučera Petr; Savický
Petr ; Vorel Vojtěch. A lower bound on CNF encodings of the at-most-one
constraint. Theoretical
Computer Science, 2018
Šíma Jiří; Savický Petr . Quasi-periodic β – expansions and cut
languages . Theoretical Computer Science, 2018Bezhanishvili Guram; Moraschini Tommaso ; Raftery
James Gordon. Epimorphisms in Varieties of Residuated
Structures. Journal of Algebra, 2017
Cabello Sergio; Cibulka Josef; Kynčl Jan; Saumell
Maria ; Valtr Pavel. Peeling Potatoes Near-Optimally in Near-Linear
Time. SIAM Journal on Computing, 2017
Hladký Jan ; Komlós J; Piguet Diana ;
Simonovits Miklos; Stein Maya; Szemerédi Endre. The approximate
Loebl-Komlós-Sós conjecture I , II , III , IV . SIAM Journal on Discrete Mathematics, 2017Moraschini Tommaso . A
Computational Glimpse at the Leibniz and Frege
Hierarchies. Annals of Pure and Applied Logic, 2017Böttcher Julia; Hladký Jan; Piguet Diana ; Taraz
Anusch. An approximate version of the tree packing
conjecture . Israel Journal of Mathematics, 2016
Haniková Zuzana; Savický Petr . Term
satisfiability in FLew-algebras. Theoretical Computer Science
31, 2016Hladký Jan; Piguet Diana . Loebl-Komlós-Sós
Conjecture: dense case. Journal of Combinatorial Theory,
2016
Chvalovský Karel; Horčík Rostislav . Full
Lambek Calculus with Contraction is Undecidable. Journal of
Symbolic Logic, 2016Moraschini Tommaso . The
Semantic Isomorphism Theorem in Abstract Algebraic
Logic. Annals of Pure and Applied Logic, 2016Strauch Oto; Porubský Štefan . Distribution of
Sequences: A Sampler. Peter Lang GmbH, Electronic revised version
December 8, 2016
Cintula Petr (ed.); Fermüller C.
(ed.); Hájek Petr (ed.), Noguera Carles (ed.). Handbook
of Mathematical Fuzzy Logic (in three
volumes). London: College Publications, 2011, 2015Cintula Petr ; Noguera Carles. A
Henkin-Style Proof of Completeness for First-Order Algebraizable
Logics. Journal of Symbolic Logic, 2015Chvalovský Karel . Undecidability
of consequence relation in Full Non-associative Lambek
Calculus. Journal of Symbolic Logic, 2015Horčík Rostislav . Word
Problem for Knotted Residuated Lattices. Journal of Pure and
applied Algebra, 2015
more
Organized Events more
