Wyniki wyszukiwania - BazTech

1

Elementary Yet PreciseWorst-Case Analysis of Floyd's Heap-Construction Program

Suchenek M. A.

Fundamenta Informaticae

|

2012

|

Vol. 120, nr 1

75-92

EN

The worst-case behavior of the heap-construction phase of Heapsort escaped mathematically precise characterization by a closed-form formula for almost five decades. This paper offers a proof that the exact number of comparisons of keys performed in the worst case during construction of a heap of size N is: 2N-2s_2(N) - e_2(N); where s_2(N) is the sum of all digits of the binary representation of N and e_2(N) is the exponent of 2 in the prime factorization of N. It allows for derivation of this best-known upper bound on the number of comparisons of Heapsort: [formula]

2

Notes on nonmonotonic autoepistemic propositional logic

Suchenek M. A.

Zeszyty Naukowe Warszawskiej Wyższej Szkoły Informatyki

|

2011

|

nr 6

74--92

EN

This paper comprises an in-depth study of semantics of autoepistemic logic that is based on author’s may years of research in the subject matter. It begins with a brief review of semantics of common patterns of nonmonotonic deduction arising from a lack of knowledge, including autoepistemic deduction, in terms of the fixed-point equation F (T, E) = E. Then it narrowly investigates minimal expansion semantics for autoepistemic propositional logic and its „only knowing” consequence operation CnAE. In particular, the following minimalknowledge assumption M K A : ϕ ∈M K A (T) iff ϕ does not add modally positive S5- consequences to T is used to syntactically characterize the operation CnAE by means of suitable completeness theorem. The paper also offers a proof that the consequence operation CnS5 of modal logic S5 is the maximal monotonic consequence operation satisfying CnS5(T) ⊆ M K A (T) for every modal theory T.

PL

Artykuł stanowi dogłębne studium semantyki logiki autoepistemicznej wykorzystujące wyniki wieloletnich badań autora w tym przedmiocie. Rozpoczyna się ono od skrótowego przeglądu semantyk powszechnie stosowanych wzorców niemonotonicznej dedukcji biorącej się z braku wiedzy, włączając w to dedukcję autoepistemiczną, w terminach równania stałopunktowego F (T, E) = E. Następnie bada ono szczegółowo semantykę minimalnych ekspansji dla zdaniowej logiki autoepistemicznej oraz jej operację CnAE odpowiadającą schematowi wnioskowania opartemu na założeniu „wiedząc tylko”. W szczególności następujące założenie M K A o minimalności wiedzy: ϕ ∈M K A (T) wtedy, i tylko wtedy, gdy ϕ nie dokłada modalnie pozytywnych S5-konsekwencji do T jest używane w celu syntaktycznego scharakteryzowania operacji CnAE przy pomocy stosownego twierdzenia o pełności. Artykuł przedstawia też dowód, że operacja konsekwencji CnS5 logiki modalnej S5 jest maksymalną monotoniczną operacją konsekwencji spełniającą CnS5(T) ⊆ M K A (T) dla każdej teorii modalnej T.

3

On Undecidability of Non-monotonic Logic

Suchenek M. A.

Studia Informatica : systems and information technology

|

2006

|

Vol. 1(7)

127--132

EN

The degree of undecidability of nonmonotonic logic is investigated. A proof is provided that arithmetical but not recursively enumerable sets of sentences definable by nonmonotonic default logic are elements of ∆n+1 but not Σ n nor Π n for some n ≥1 in Kleene- Mostowski hierarchy of arithmetical sets.