Výpočetní složitost substrukturálních logik - NLTM039

• Anglický název: Computational complexity of substructural logics
• Zajišťuje: Informatický ústav Univerzity Karlovy (32-IUUK)
• Fakulta: Matematicko-fyzikální fakulta
• Platnost: od 2014 do 2015
• Semestr: zimní
• E-Kredity: 3
• Rozsah, examinace: zimní s.:2/0, Zk [HT]
• Počet míst: neomezen
• Minimální obsazenost: neomezen
• 4EU+: ne
• Virtuální mobilita / počet míst pro virtuální mobilitu: ne
• Stav předmětu: vyučován
• Jazyk výuky: čeština
• Způsob výuky: prezenční
• Způsob výuky: prezenční
• Další informace: http://v roce 2014/2015 nebude předmět vyučován
• Garant: RNDr. Zuzana Haniková, Ph.D.
• Třída: Informatika Mgr. - volitelný
• Kategorizace předmětu: Informatika > Teoretická informatika

Anotace

čeština

Poslední úprava: IUUK (21.03.2013)

Přednáška ukáže některé typické rozhodovací problémy v známějších substrukturálních logikách, s důrazem na jejich výrokovou část, a bude se věnovat jejich klasifikaci z hlediska výpočetní složitosti (ev. algoritmické rozhodnutelnosti). Výchozím bodem budou dobře známé výsledky týkající se logiky klasické. Následně přejde k logickým systémům formálně slabším, jako např. logice intuicionistické a jejím dalším oslabením nebo rozšířením, nebo známějším fuzzy logikám.

angličtina

Poslední úprava: IUUK (25.03.2013)

The lecture will present some typical decision problems related to substructural logics, dealing with their classification from the point of view of computational complexity (and possibly algorithmic undecidability). We will use well known results on classical logic as our starting point. Then we will proceed towards formally weaker logical systems, such as intuitionistic logic and its further weakenings or extensions, as well as some of the more familiar fuzzy logics.

Literatura

čeština

Poslední úprava: IUUK (11.04.2013)

1. N.Galatos, P. Jipsen, T. Kowalski, H. Ono: Residuated Lattices: An Algebraic Glimpse at Substructural Logics. Elsevier, 2007
2. O. Kharlampovich, M. Sapir: Algorithmic problems in varieties.
3. A. Chagrov, M. Zakharyaschev: Modal Logic. Oxford Logic Guides. Vol. 35, Clarendon Press, 1997.
4. P. Cintula, P. Hájek, C. Noguera (ed.): Handbook of Mathematical Fuzzy Logic. College Publications, 2011.
5. R. Horčík, K. Terui: Disjunction Property and Complexity of Substructural Logics. Theoretical Computer Science, 412(31):3992-4006, 2011.

Sylabus

čeština

Poslední úprava: IUUK (25.03.2013)

Rozhodovací problémy v logice, související rozhodovací problémy v univerzální algebře a teorii důkazů. Další související vlastnosti logik. Některá specifika neklasických logik. Fragmenty logik a algebraických teorií. Algebraická sémantika substrukturálních logik.

Konkrétně budou zkoumány především:

• klasická logika;

• intuicionistická logika;

• Flew (Full Lambek calculus with Exchange and Weakening);

• FL (Full Lambek calculus);

• Łukasiewiczova logika.

angličtina

Poslední úprava: IUUK (25.03.2013)

Decision problems in logic and related decision problems in universal algebra and proof theory. Related properties of logics. Some specifics of non-classical logics. Fragments of logics and algebraic theories. Algebraic semantics of substructural logics.

Specifically, we will focus on:

• classical logic;

• intuitionistic logic;

• Flew (Full Lambek calculus with Exchange and Weakening);

• FL (Full Lambek calculus);

• Łukasiewicz logic.

Vstupní požadavky

čeština

Poslední úprava: IUUK (25.03.2013)

U studentů se předpokládá znalost běžného aparátu klasické logiky. Výhodou budou znalosti základních pojmů z výpočetní složitosti, univerzální algebry a teorie důkazů, event. předchozí zkušenost s neklasickými logikami.

angličtina

Poslední úprava: IUUK (25.03.2013)

Basic familiarity with the apparatus of classical logic will be assumed. Knowledge of basic concepts of computational complexity, universal algebra or proof theory, as well as previous experience with non-classical logics, will be an advantage.