Michal Walicki

Address: University of Bergen 
         Department of Informatics
         HiB, 5020 Bergen, NORWAY
Ph.       : +47 55 58-41-78
Fx.       : +47 55 58-41-99
E-mail : myforename-at-ii-dot-uib-dot-no

Interests: self-reference and semantic closure, digraph kernels, paraconsistency. 
more specifically: 

(CURRENT) Graph representation of logical theories:
    Classical/paraconsistent semantics represented by digraph kernels/semikernels
    Graph Normal Form and its applications
    Logical circularity as graph cycles 
    Semantic paradoxes, self-reference
    
 The earlier conjecture:
    A digraph with no kernel has an odd cycle or
    a ray with infinitely many vertices dominating it.
 has been proven for: 

  1. graphs with finite number of ends (Discrete Mathematics, 2019)

  2. A  variant of Poison Game, introduced by Duchet and Meyniel for finite digraphs,
     which can be useful for proving (non)existence of (semi)kernels on infinite digraphs.


 
(PAST) Universal algebra and category theory:    
    Categories of multialgebras
    Relational and power structures
    Algebraic treatment of nondeterminism

Some papers:

1. Logic

Self-reference, paradoxes, infinitary theories and kernels of digraphs

(about third part of these are joint works with Sjur Dyrkolbotn)
1. Reference graphs, dependence relations and kernel theory in analysis of paradoxes, a note on some relations between the three. [unpublished]
2. "Extensions in Graph Normal Form" - graph normal form for first-order logic, with applications to (conservative) extensions [Logic Journal of the IGPL, Vol. 30, No. 1, pp.101-123, 2022]
3. "Resolving infinitary paradoxes", complete reasoning with classical resolution about and in the presence of inconsistency [preprint, final version in Journal of Symbolic Logic, 82,(2),2017,709-723]
4. Paraconsistent resolution and semantics, refining the above: maximal, predecessor-closed local kernels provide general semantics for the resolution logic; when the theory is consistent, they coincide with the classical semantics, while otherwise provide a classical semantics for the maximal consistent subdiscourse (kernel for maximal ``consistent'' induced subgraph); [Australasian Journal of Logic, Vol. 19 No. 3, 2022]
5. "Propositional Discourse Logic": graph structure of paradoxes, diagnosis of semantic paradoxes [preprint; appeared in Synthese, 2013]
6. Argumentation, paradox and kernels in directed graphs - a Ph.D. thesis by Sjur Dyrkolbotn, written (and defended) under my supervision in 2012.
7. "Reference, paradoxes and truth", graph-based (or boolean equations based) approach to paradoxes of self-reference. Many cases problematic for earlier approaches are solved in a simple way. [preprint; the final version in Synthese, available at www.springerlink.com or at JStore, 2009.]

Kernels of digraphs (paradoxes and satisfiability)

10. A variant of Poison Game, introduced by Duchet and Meyniel for finite digraphs, which can be useful for proving (non)existence of (semi)kernels on infinite digraphs. Nonexistence of any semikernel amounts to player B winning always in finitely many steps.
11. Kernels of digraphs with finitely many ends, a proof of the main conjecture (top of this page) for graphs with finitely many ends, [preprint; Discrete Mathematics, 342, 473-486, 2019]
12. Graph Normal Form for propositional logic and some reverse mathematical results, at APAL, vol. 162, no. 3, March 2012
13. "Finding kernels or solving SAT": analysing the relations between the algorithms for kernels and SAT, [Journal of Discrete Algorithms, vol.10, 146-164, 2012]

Modal / Epistemic / Sequence logic / Bounded (finite) agents

-- Sequence Logic

13. "A strongly complete logic of dense time intervals", ESSLI-06, (logic relating sequential descriptions (in an arbitrary parameter logic) of systems passing through changing states)
14. "Developing Bounded Reasoning" (a preliminary version, 2008. The original publication is available at www.springerlink.com)
15. "Completeness and decidability in Sequence Logic" , LPAR'07
16. "Modalities as Interactions between the Classical and the Intuitionistic Logics", Tech.Rep. no.330, June 2006, (in the classical algebraic semantics, modalities can be viewed as combinations of classical and intuitionisitc negations)
    • abbreviated version published in the journal Logic and Logical Philosophy, 2007

-- Bounded agents and finite sets

17. Strongly Complete Axiomatizations of ``Knowing At Most'' in Standard Syntactic Assignments, CLIMA'05.
18. Complete Axiomatization of Finite Syntactic Epistemic States, in Declarative Agent Languages and Technologies, workshop at AAMAS'2005.
19. "The Logic of Finite Syntactic States"
    (a Ph.D. thesis written under my supervision by Thomas AAgotnes, 2004 (epistemic logic of finite agents with bounded resources) with a small errata)
20. "Developing Bounded Reasoning" (a preliminary version, 2008. The original publication is available at www.springerlink.com)
21. Complete axiomatisations of properties of finite sets, Logic Journal of the IGPL, vol.16, no.3, June 2008.

Logic of multifunctions

22. Quantifier-free logic for multialgebraic theories, WOLLIC, 2003 [revised version in Theoretical Computer Science, 2006]
23. "A Complete Calculus for the Multialgebraic and Functional Semantics of Nondeterminism" [ACM TOPLAS, Vol. 17, No. 2, March 1995],
24. A digression:"On Specialization of Derivations in Axiomatic Equality Theories" [in Proc. of LFCS'94,LNCS vol. 813, 1994]
25. "Multialgebras, Power Algebras and Complete Calculi of Identities and Inclusions" [ADT'94, in Recent Trends in Data Type Specification,LNCS, vol. 906, 1995]

-- Rewriting in multialgebras

26. "Reasoning and Rewriting with Set-Relations I: Ground Completeness" [Proc. of CSL'94, L.Pacholski, J.Tiuryn (eds.), LNCS vol. 933, 1995]
    - ps file or a longer version with more proofs
27. "Reasoning and Rewriting with Set-Relations II: Completeness for the Non-Ground Case" [Recent Trends in Data Type Specification, LNCS. vol.1130, (eds. M.Haveraaen, O.Owe, O.-J.Dahl), Oslo, 1995]
28. "Nondeterministic Algebraic Specifications in Relational Syntax" [Proc. of Nordic Workshop on Programming Theory, B.Bjerner, M.Larsson, B.Norstroem (eds.), Rep. 86, The Programming Methodology Group, Goeteborg University, pp.185-203, 1996]

2. Algebra, semantics

Relations, multifunctions, homomorphisms, universal multialgebra

29. "Universal Multialgebra", summarises all earlier results, presenting an interesting notion of multialgebraic homomorphism and congruence. A revised version appears as a chapter in "New Topics in Theoretical Computer Science", Nova Science Publishers, 2008.
30. "Bireachability and final multialgebras" [Proceedings of CALCO'05, LNCS 3629]
31. "A category for studying the standarization of reporting languages" [TR, also in Proceedings of the 9th Asian Conference on Logic]
32. "Compositional Homomorphisms of Relational Structures", FTC 2001
    
33. "The institution of Multialgebras - a general framework for algebraic software development"
    (a Ph.D. thesis written under my supervision by Yngve Lamo, 2003)
34. A digression: "Computation Algebras" [Tech. Rep. no. 117, Dept. of Informatics, University of Bergen, 1996], appeared in Mathematical Structures in Computer Science, 2001

Multialgebraic semantics of nondeterminism

35. "Algebraic Approaches to Nondeterminism - an Overview" [ACM Computing Surveys,29, 1, March, 1997]
36. "Generated Models and the Omega-rule: the Nondterministic Case" [Proc. of TAPSOFT'95, LNCS, vol. 915, 1995]
37. "Multialgebras, Power Algebras and Complete Calculi of Identities and Inclusions" [ADT'94, in Recent Trends in Data Type Specification,LNCS, vol. 906, 1995]
38. "Initiality + Nondeterminism => Junk" [in Proc. of NIK'94,Tapir, 1994]
39. "Singular and Plural Nondeterministic Parameters" [SIAM Journal on Computing, 26-3, 1997 (1995)]
40. "Nondeterminism vs. Underspecification", SCI 2001

Applications and extensions of nondeterministic specifications

41. "Structured Specifications and Implementation of Nondeterminisitc Data Types" [Tech. Rep. TUM-I9442, Inst. fur Informatik, Technische Universitat Munchen, 1994], appeared also in Nordic Journal of Computing, no. 2, 1995.
42. "Modeling partiality by nondeterminism" [Tech. Rep. 178, Department of Informatics, University of Bergen, 1999.
43. "Combining specification formalisms in the `general logic' of multialgebras", FLIRTS 2002 (2003).
44. "Composition and refinement of specifications of parameterized data types", REFINE 2002.
45. Specification of Parameterized Programs - persistency revisited, Nordic Journal of Computing, 2001.

3. Lecture Notes:

46. INF-227 - Introduction to mathematical logic
    • the complete text published as a book by World Scientific
    • a preliminary version with most of the syllabus (and an extensive section on the history of logic)
    • a short errata
47. INF-220 - Algebraic Specification:
    • "Universal Algebra and ADTs" (Draft, I-220, 1996)
48. INF-121 (h-2005)
    • 02. Rekursjon
    • 02. RekursjonTR

4. Other things:

1. philosophy, skiing.



You are the visitor number , since 20.05.2017.