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 cycles in language graph 
    Semantic paradoxes, self-reference, definability of truth
    

 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 in the 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, truth theory and kernels of digraphs

    (about third part of these are joint works with Sjur Dyrkolbotn)
    1. Truth is definable in Logic of Sentential Operators, LSO (introduced in the paper below), without deviating from classical logic, (2025).
    2. Logic of sentential operators, LSO, extends LK with 2 rules for sentential quantifiers, providing a complete reasoning for the language extending any FOL language with operators and quantification over sentences. Graph-based semantics admits self-reference arising from the unrestricted sentential quantification. Paradoxes are distinct from contradictions and do not lead to explosion, unless unrestricted (cut) is added to LSO. The final version in Journal of Philosophical Logic, Vol. 53, pp.1579–1639, (2024).
    3. Reference graphs, dependence relations and kernel theory in analysis of paradoxes, a note on some relations between the three. [unpublished]
    4. "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]
    5. "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]
    6. 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]
    7. "Propositional Discourse Logic": graph structure of paradoxes, diagnosis of semantic paradoxes [preprint; appeared in Synthese, 2013]
    8. Argumentation, paradox and kernels in directed graphs - a Ph.D. thesis by Sjur Dyrkolbotn, written (and defended) under my supervision in 2012.
    9. "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)

    1. 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.
    2. 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]
    3. Graph Normal Form for propositional logic and some reverse mathematical results, at APAL, vol. 162, no. 3, March 2012
    4. "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

    1. "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)
    2. "Developing Bounded Reasoning" (a preliminary version, 2008. The original publication is available at www.springerlink.com)
    3. "Completeness and decidability in Sequence Logic" , LPAR'07
    4. "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)

    -- Bounded agents and finite sets

    1. Strongly Complete Axiomatizations of ``Knowing At Most'' in Standard Syntactic Assignments, CLIMA'05.
    2. Complete Axiomatization of Finite Syntactic Epistemic States, in Declarative Agent Languages and Technologies, workshop at AAMAS'2005.
    3. "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)
    4. "Developing Bounded Reasoning" (a preliminary version, 2008. The original publication is available at www.springerlink.com)
    5. Complete axiomatisations of properties of finite sets, Logic Journal of the IGPL, vol.16, no.3, June 2008.

    Logic of multifunctions

    1. Quantifier-free logic for multialgebraic theories, WOLLIC, 2003 [revised version in Theoretical Computer Science, 2006]
    2. "A Complete Calculus for the Multialgebraic and Functional Semantics of Nondeterminism" [ACM TOPLAS, Vol. 17, No. 2, March 1995],
    3. A digression:"On Specialization of Derivations in Axiomatic Equality Theories" [in Proc. of LFCS'94,LNCS vol. 813, 1994]
    4. "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

    1. "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
    2. "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]
    3. "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

    1. "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.
    2. "Bireachability and final multialgebras" [Proceedings of CALCO'05, LNCS 3629]
    3. "A category for studying the standarization of reporting languages" [TR, also in Proceedings of the 9th Asian Conference on Logic]
    4. "Compositional Homomorphisms of Relational Structures", FTC 2001
    5. "The institution of Multialgebras - a general framework for algebraic software development"
      (a Ph.D. thesis written under my supervision by Yngve Lamo, 2003)
    6. 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

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

    Applications and extensions of nondeterministic specifications

    1. "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.
    2. "Modeling partiality by nondeterminism" [Tech. Rep. 178, Department of Informatics, University of Bergen, 1999.
    3. "Combining specification formalisms in the `general logic' of multialgebras", FLIRTS 2002 (2003).
    4. "Composition and refinement of specifications of parameterized data types", REFINE 2002.
    5. Specification of Parameterized Programs - persistency revisited, Nordic Journal of Computing, 2001.

    3. Lecture Notes:

    1. INF-227 - Introduction to mathematical logic
    2. INF-220 - Algebraic Specification:
    3. INF-121 (h-2005)

    4. Other things:

    1. philosophy, telemark skiing.