Oddělení teoretické informatiky
Členové našeho oddělení se zaměřují na základní aspekty teoretické informatiky a jejich práci lze klasifikovat do tří hlavních oblastí: kombinatorika, matematická logika, výpočetní složitost . Naším cílem v těchto oblastech je nejen dosahovat nových výsledků, ale také rozšiřovat repertoár přístupů, které jsou považovány za standardní. Konkrétně sledujeme tři hlavní cíle:
Kombinatorika: studovat současné zásadní problémy extremální teorie grafů a diskrétních náhodných struktur, a přispět tak k těmto centrálním tématům kombinatoriky, které jsou klíčové například pro naše porozumění velmi velkým sítím.
Matematická logika: vyvinout a aplikovat neklasické logiky pro usuzování v přírozených i umělých scénářích s informacemi z reálného světa, které jsou často nejisté, stupňované nebo dokonce protichůdné a mění se v čase.
Výpočetní složitost: prohloubit naše znalosti standardních i nestandardních výpočetních modelů s přihlédnutím nejen k obvyklým mírám složitosti, jako je čas a prostor, ale i k novým, které jsou relevantní pro složitost algoritmů konkrétních úloh v neurovýpočtech, kompilaci znalostí a kombinatorické optimalizaci.
Kombinatorika: Extremální teorie grafů, regularita, pravděpodobnostní metoda, limity grafů, náhodné grafy, diskrétní struktury, výpočetní geometrie, kombinatorické a algebraické metody v teorii čísel.
Matematická logika: Logika a usuzování, stupňované pojmy, vágnost, nejistota, matematická fuzzy logika, substrukturální logiky, parakonzistentní logiky, dynamické a nemonotónní logiky, modální logiky, abstraktní algebraická logika, složitost neklasických logik, filozofie matematiky.
Výpočetní složitost: branching programy, neuronové sítě, booleovské funkce, síla propagace v instancích pro problém SAT, kompilace znalostí, logické popisy výpočtů, energetická složitost.
Garbe Frederik; Hladký Jan ; Šileikis Matas ; Skerman Fiona. From flip processes to dynamical systems on graphons. Annales de l'Institut Henri Poincaré, Probabilités et Statistiques, 2024
Bílková Marta ; Fritella Sabine; Kozhemiachenko Daniil; Majer Ondrej ; Nazari Sajad. Reasoning with belief functions over Belnap-Dunn logic. Annals of Pure and Applied Logic, 2024Ferenz Nicholas . One Variable Relevant Logics are S5ish. Journal of Philosophical Logic, 2024Sedlár Igor ; Vigiani Pietro. Epistemic Logic for Relevant Reasoners. Journal of Philosophical Logic, 2024Moraschini Tommaso; Wannenburg Johann Joubert ; Yamamoto Kentarô . Elementary Equivalence in Positive Logic via Prime Products. Journal of Symbolic Logic, 2024
Campos Araújo Pedro ; Hladký Jan ; Hng Eng Keat ; Šileikis Matas . Prominent examples of flip processes. Random Structures and Algorithms, 2024Garbe Frederik; Hladký Jan ; Kun Gábor; Pekárková Kristýna. On pattern-avoiding permutons. Random Structures and Algorithms, 2024
Braunfeld Samuel Walker . Decidability in geometric grid classes of permutations. Proceedings of the American Mathematical Society, 2024Cintula Petr ; Metcalfe George; Tokuda Naomi. One-variable fragments of first-order logics. Bulletin of Symbolic Logic, 2024Fussner Daniel Wesley ; Galatos Nikolaos. Semiconic idempotent logic I: Structure and local deduction theorems. Annals of Pure and Applied Logic, 2024Šíma Jiří ; Vidnerová Petra; Mrázek Vojtěch. Energy complexity of convolutional neural networks. Neural Networks, 2024Yamamoto Kentarô . The Small Index Property of the Fraïssé limit of Finite Heyting Algebras. Journal of Algebra, 2023Přenosil Adam . The Lattice of Super-Belnap Logics. Review of Symbolic Logic, 2023Bílková Marta ; Sedlár Igor . Epistemic Logics of Structured Intensional Groups. Proceedings Nineteenth conference on Theoretical Aspects of Rationality and Knowledge (TARK 2023), 2023Fernández-Duque David ; Gougeon Quentin. Fixed Point Logics on Hemimetric Spaces. 38th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS) Proceedings, 2023Yamamoto Kentarô . The Automorphism Group of The Fraïssé Limit of Finite Heyting Algebras. Journal of Symbolic Logic, 2023Lang Richard; Sanhueza-Matamala Nicolás . On sufficient conditions for spanning structures in dense graphs . Proceedings of the London Mathematical Society, 2023
Pavez-Signé Matias; Sanhueza-Matamala Nicolás ; Stein Maya. Towards a hypergraph version of the Pósa-Seymour conjecture. Advances in Combinatorics, 2023
Piga Simón; Sanhueza-Matamala Nicolás . Cycle Decompositions in 3-Uniform Hypergraphs. Combinatorica, 2023
Grebík Jan; Rocha Israel . Fractional Isomorphism of Graphons. Combinatorica, 2022
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, 2022Cintula 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, 2021Bose 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; Szemeredi 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
více
Kmenoví zaměstnanci
Mgr. Marta Bílková, Ph.D. Samuel Walker Braunfeld, Ph.D. Ing. Wesley Fussner, Ph.D. RNDr. Zuzana Haniková, Ph.D. Mgr. Jan Hladký, Ph.D. Mgr. Roman Kuznets, Ph.D. Mgr. Diana Piguet, Ph.D. RNDr. Petr Savický, CSc. Mgr. Igor Sedlár, Ph.D. Matas Šileikis, Ph.D. doc. RNDr. Jiří Šíma, DrSc.
Vedoucí oddělení: Mgr. Diana Piguet, Ph.D.
Zástupce vedoucího oddělení: Mgr. Igor Sedlár, Ph.D.
Sekretářka: Ing. Hana Stříhavková, Ph.D.
Ústav informatiky
