Complexity Issues in Basic Logic

0405291 - UIVT-O 330612 RIV DE eng J - Journal Article
Aguzzoli, S. - Gerla, B. - Haniková, Zuzana
Complexity Issues in Basic Logic.
[Logika BL z hlediska výpočetní složitosti.]
Soft Computing. Roč. 9, - (2005), s. 919-934. ISSN 1432-7643. E-ISSN 1433-7479
R&D Projects: GA MŠMT LN00A056
Institutional research plan: CEZ:AV0Z10300504
Keywords : basic fuzzy logic (BL) * computational complexity * functional representation
Subject RIV: BA - General Mathematics
Impact factor: 0.538, year: 2005

We survey complexity results concerning a family of propositional many-valued logics. In particular, we shall address satisfiability and tautologousness problems for Hájek's Basic Logic BL and for several of its schematic extensions. We shall review complexity bounds obtained from functional representation results, as well as techniques for dealing with non-trivial ordinal sums of continuous t-norms.

Podáváme přehled výsledků o výpočetní složitosti jisté skupiny výrokových vícehodnotových logik. Konkrétně se budeme zabývat problémy splnitelnosti a tautologičnosti pro Hájkovu logiku BL a některá její schematická rozšíření. Věnujeme se přitom odhadům získaným na základě funkční reprezentace a technikám, které umožňují pracovat s netriviálními ordinálními součty t-norem.
Permanent Link: http://hdl.handle.net/11104/0125472