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 vztahů mezi třídami složitosti pomocí standardních i nestandardních výpočetních modelů s přihlédnutím nejen k obvyklým měřítkům složitosti, jako je čas nebo prostor, ale i k novým, která jsou relevantní v neurovýpočtech a kompilaci znalostí.

Oblasti výzkumu

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.

Výpočetní složitost: branching programy, neuronové sítě, booleovské funkce, příprava instancí pro problém SAT, kompilace znalostí, logické popisy výpočtů, nestandardní číselné systémy.

Pracovní skupiny a jejich semináře

Kombinatorická skupina: skupina zaměřená na studium extremální teorie grafů, diskrétních struktur, limity grafů a výpočetní geometrie. Pořádáme kombinatorický seminář.

LogICS: skupina se věnuje studiu (neklasické) logiky. Společně s Českou společností pro kybernetiku a informatiku pořádáme seminář aplikované matematické logiky (nazývaný též Hájkův seminář podle svého zakladatele), který se pravidelně koná od konce šedesátých let.

Aktuální projekty (více info)

• Limity grafů a související obory (2021-2025; GAČR)
• AppNeCo: Aproximativní neurovýpočty (2022-2024; GAČR)
• GRADLACT: Stupňované logiky konání (2022-2024; GAČR)
• Metamatematika substrukturálních modálních logik (2022-2024; GAČR)
• MOSAIC Modalities in Substructural Logics: Theory, Methods and Applications (2021-2024; EU)
• Náhodné diskrétní struktury (2020-2022, GAČR)
• Podpora internacionalizace ÚI AV ČR, v.v.i. (2020-2022, MŠMT ČR)
• FoNeCo: Analytické základy neurovýpočtů (2019-2021; GAČR)
• Národní centrum kompetence – Kybernetika a umělá inteligence (2019-2021; GAČR)
• Reprezentace booleovských funkcí úplné vzhledem k jednotkové propagaci (2019-2021; GAČR)
• Strukturální vlastnosti viditelnosti terénů a Voroného diagramů nejvzdálenější barvy (2019-2021; GAČR)
• Substrukturální modální logiky pro reprezentaci znalostí (2020-2021; AV ČR)
• Vnořování, pakování a limity v grafech (2019-2021; GAČR)
• CONNECT – Combinatorics of Networks and Computation (2017-2020; H2020 MSCA RISE)
• Neklasické logické modely informační dynamiky (2018-2020; GAČR)
• Rozvoj lidských zdrojů pro výzkum v teoretické informatice (2018-2020; MŠMT)
• Usuzování se škálovanými vlastnostmi (2018-2020; GAČR)
• Predikátové škálované logiky a jejich aplikace v informatice (2017-2019; GAČR)
• SYSMICS: Syntax a sémantika: Metody, interakce a souvislosti v substrukturálních logikách (2016-2019; GAČR)
• Centrum excelence – Institut teoretické informatiky (CE-ITI) (2012-2018; GAČR)
• Extremální teorie grafů a aplikace (2016-2018; GAČR)
• Reasoning with Incomplete and Inconsistent Information (AV ČR, 2017)
• Modelování vágních kvantifikátorů v matematické fuzzy logice (2015-2017; GAČR)
• Neklasické výrokové a predikátové logiky: přístup založený na uspořádání (2013-2016; GAČR)
• Algebraické metody v teorii důkazů (2011-2015; GAČR)
• Distribuční a metrické vlastnosti číselných posloupností a jejich aplikace (2012-2015; GAČR)

více

Vybrané publikace

• 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; Szemeredi 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

více

Organizované akce

• 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

více