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írá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, filozofie matematiky.
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.
Koaliční a epistemické logiky: intenzionální přístup ke skupinám (2022-2025; LA GAČR-DFG)
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
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, 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
Ší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; 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
Organizované akce více
