The set of PrAl+valid in a finite structure is undecidable

• Autorzy: Borowska A.

Warianty tytułu

PL

Zbiór formuł logiki PrAl+ prawdziwych w skończonej strukturze jest nierozstrzygalny

• Języki publikacji: EN

Abstrakty

EN

We consider a probabilistic logic of programs. In it is proved that the set of formulas of the logic PrAL, valid in a finite structure, is decidable with respect to the diagram of the structure. We add to the language LP of PrAL a sign S and a functor lg. Next we justify that the set of formulas of extended logic, valid in a finite at least 2-element structure (for LP+) is undecidable.

PL

Rozważamy probabilistyczną logikę algorytmiczną. W pracy znajduje się uzasadnienie, że zbiór formuł logiki PrAL, prawdziwych w skończonej strukturze, jest rozstrzygalny ze względu na diagram struktury. Dodajemy do języka LP logiki PrAL znak S i funktor lg. Następnie uzasadniamy, ze zbiór formuł rozszerzonej logiki, prawdziwych w skończonej co najmniej 2-elementowej strukturze (dla L P+), nie jest już rozstrzygalny.

Słowa kluczowe

EN

Probabilistic Algorithmic Logic; existential iteration quantifier

PL

probabilistyczna logika algorytmiczna; kwantyfikator egzystencjalny iteracji

• Wydawca: Oficyna Wydawnicza Politechniki Białostockiej
• Czasopismo: Advances in Computer Science Research
• Rocznik: 2013
• Tom: Nr 10
• Strony: 5--18
• Opis fizyczny: Bibliogr. 14 poz.

Twórcy

autor

Borowska A.

• Faculty of Computer Science, Bialystok University of Technology, Białystok, Poland

Bibliografia

• [1] L. Banachowski, Investigations of Properties of Programs by Means of the Extended Algorithmic Logic, Fundamenta Informatica, 1 (1977), p. 167–193.
• [2] J. Barwise, Handbook of Mathematical Logic, Elsevier Science Publishers B.V., 1983.
• [3] A. Borowska, Algorithmic Information Theory, Computer Information Systems and Industrial Management Applications, 2003, p. 5–31.
• [4] A. Borowska, Algebraic Methods of Determining of Transition Probabilities in Probabilistic Algorithms, Conference Materials of XV FIT, 2004, p. 148–157.
• [5] A. Borowska, Selected Problems of the Probabilistic Algorithms and the Markov Chains. Reduction of Valuations, Ph.D. Thesis, Technical University of Bialystok, 2010.
• [6] W. Danko, The set of Probabilistic Algorithmic Formulas Valid in a Finite Structure is Decidable with Respect to its diagram, Fundamenta Informatica, Vol. 19 (1993), p. 417–431.
• [7] A. Grzegorczyk, An Outline of Theoretical Arithmetics, PWN, Warsaw 1971.
• [8] J. Koszelew, The Methods of Analysis of Properties of Probabilistic Programs Interpreted in Finite Fields, Ph.D. Thesis, PAN, 2000.
• [9] A. Kreczmar, Effectivity problems of algorithmic logic, Automata, Languages and Programming, Lecture Notes in Computer Science, Vol. 14 (1974), Publisher Springer Berlin Heidelberg, p. 584–600.
• [10] A. Kreczmar, The Set of all Tautologies of Algorithmic Logic is Hyperarithmetical, Bull. Acad. Polon. Sci., Ser. Math. Astron. Phys., 21 (1971), p. 781–783.
• [11] R. C. London, About Mathematical Logic, PWN, Warsaw, 1968.
• [12] G. Mirkowska, A. Salwicki, Algorithmic Logic, PWN-Polish Scientific Publishers, 1987.
• [13] G. Mirkowska, A. Salwicki, Algorithmic Logic for Programmers, WN-T, Warsaw, 1992.
• [14] A. Rutkowski, Elements of Mathematical Logic, WSiP, Warsaw, 1978.