- Home
- Institute
- People
- Research
- Applications
- Seminars and Events
- Library
- Doctoral Studies
- Jobs

Institute of Computer Science

The Czech Academy of Sciences

The Czech Academy of Sciences

"The question of whether Machines Can Think... is about as relevant as the question of whether Submarines Can Swim." - E. W. Dijkstra

Research Areas | Work Groups and Their Seminars | Recent Projects | Selected Publications | Organized Events | Department Members |

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.

*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.

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.

- 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)

**Cintula Petr**; Noguera Carles. Logic and Implication: An Introduction to the General Algebraic Study of Non-classical Logics. Springer, 2021- Dolež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- Badia G.;
**Cintula Petr; Hájek Petr; Tedder Andrew**. How Much Propositional Logic Suffices for Rosser’s Undecidability Theorem? Review of Symbolic Logic, 2020 - 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, 2020**Moraschini Tommaso**; Wannenburg J. J. Epimorphism Surjectivity in Varieties of Heyting Algebras. Annals of Pure and Applied Logic, 2020**Sedlár Igor; Tedder Andrew**. Lambek Calculus with Conjugates. Studia Logica, 2020**Šíma Jiří**. Analog Neuron Hierarchy. Neural Networks, 2020- Allen 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, 2019**Moraschini Tommaso**. On the complexity of the Leibniz hierarchy. Annals of Pure and Applied Logic, 2019**Rozhoň 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, 2019- Kuč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, 2018- Bezhanishvili 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, 2017**Moraschini Tommaso**. A Computational Glimpse at the Leibniz and Frege Hierarchies. Annals of Pure and Applied Logic, 2017**Šíma Jiří; Žák Stanislav**. On tight separation for Blum measures applied to Turing machine buffer complexity. Fundamenta Informaticae, 2017- Bö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, 2016- Hladký 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, 2016**Moraschini Tommaso**. The Semantic Isomorphism Theorem in Abstract Algebraic Logic. Annals of Pure and Applied Logic, 2016- Strauch 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, 2015**Cintula Petr**; Noguera Carles. A Henkin-Style Proof of Completeness for First-Order Algebraizable Logics.Journal of Symbolic Logic, 2015**Chvalovský Karel**. Undecidability of consequence relation in Full Non-associative Lambek Calculus. Journal of Symbolic Logic, 2015**Horčík Rostislav**. Word Problem for Knotted Residuated Lattices. Journal of Pure and applied Algebra, 2015

- Kurt Gödel Day and Czech Gathering of Logicians 2021
- 3rd DaLí Workshop. Dynamic Logic: New Trends and Applications 2020
- Nonclassical Logics and Judgement Aggregation 2019
- Workshop on Admissible Rules and Unification 2019
- Prague Gathering of Logicians 2019
- Prague Logic Camp 2019
- PhDs in Logic X 2018
- Prague Gathering of Logicians and Beauty of Logic 2018
- 23rd Czech and Slovak International Conference on Number Theory 2017
- Topology, Algebra, and Categories in Logic 2017
- Non-classical Modal and Predicate Logics 2017
- Prague seminar: The Future of Mathematical Fuzzy Logic 2016
- Prague Gathering of Logicians 2015
- Prague seminar on Non-Classical Mathematics 2015
- 4th International Conference on Uniform Distribution Theory 2014
- Prague Seminar on Substructural Logics 2014
- 2nd Prague Symposium on Semilinear Logics 2013
- 21st Czech and Slovak International Conference on Number Theory 2013
- Gathering of Prague-Based Logicians 2013
- Manyval 2013
- ALANT Joint Conferences on Algebra, Logic and Number Theory 2012
- 20th Czech and Slovak International Conference on Number Theory 2011
- Logic, Algebra and Truth Degrees 2010
- 19th Czech and Slovak International Conference on Number Theory 2009
- 9th Central European Conference on Cryptography 2009
- 5th Polish, Slovak and Czech Conference on Number Theory 2004

- Marta Bílková
- Pedro Campos Araújo
- Nicholas Ferenz
- Thomas Macaulay Ferguson
- David Fernández Duque
- Zuzana Haniková
- Jan Hladký
- Eng Keat Hng
- Filip Jankovec
- Tomas Juškevičius
- Vahideh Keikha
- Chun Yu Lin
- Ondrej Majer
- Eva Martinčíková
- Diana Piguet
- Štefan Porubský
- Adam Přenosil
- Hanka Řada
- Petr Savický
- Igor Sedlár
- Mariia Shyian
- Matas Šileikis
- Gopal Viswanathan
- Kentaro Yamamoto
- Stanislav Žák

**Head: **Jiří Šíma

**Secretarial support: **Kateřina Vacková