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 : michal(at)ii(dot)uib(dot)no

Interests: Logical methods in software development and modeling, 
more specifically (in order of current importance):
- Logic: 
    Equivalence of SATisfiability and the existence of digraph kernels
    Paradoxes of self-reference
    
 The current conjecture:
    If a dag has no kernel then its underlying undirected graph has
        a complete infinite graph as a (topological) minor. 
    
(PAST):
- Universal algebra and category theory:    
    Categories of multialgebras
    Relational and power structures
    Algebraic treatment of nondeterminism

Lecture Notes:

1. 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)
2. INF-220 - Algebraic Specification:
   • "Universal Algebra and ADTs" (Draft, I-220, 1996)
3. INF-121 (h-2005)
   • 02. Rekursjon
   • 02. RekursjonTR

Some papers:

Algebra, semantics

Multialgebraic semantics of nondeterminism

1. "Algebraic Approaches to Nondeterminism - an Overview"
   [ACM Computing Surveys,29, 1, March, 1997]
   • view the .ps file
   • ftp the .ps file

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]
   • read the abstract
   • view the .ps file
   • ftp the .ps file

4. "Initiality + Nondeterminism => Junk" [in Proc. of NIK'94,Tapir, 1994]
   • view the .ps file
   • ftp the .ps file

5. "Singular and Plural Nondeterministic Parameters"
   [SIAM Journal on Computing, 26-3, 1997 (1995)]
   • view the .ps file
   • ftp the .ps file

6. "Nondeterminism vs. Underspecification", SCI 2001

7. "The Institution of Multialgebras"
   Tech.Rep. no.209, Department of Informatics, University of Bergen, 2000
   • view the .ps file

   More semantics (relations, multifunctions, universal algebra)

8. "Relations, Multialgebras and Homomorphism"
   • "Bireachability and final multialgebras" [Proceedings of CALCO'05, LNCS 3629]
   • "A category for studying the standarization of reporting languages" [Proceedings of the 9th Asian Conference on Logic]
   • "Compositional Homomorphisms of Relational Structures", FTC 2001
     
   • "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.

9. "The institution of Multialgebras - a general framework for algebraic software development"
   (a Ph.D. thesis written under my supervision by Yngve Lamo, 2003)

10. "Computation Algebras"
    [Tech. Rep. no. 117, Dept. of Informatics, University of Bergen, 1996]
    • view the .ps file, Mathematical Structures in Computer Science, 2001

    Applications and extensions of nondeterministic specifications

11. "Structured Specifications and Implementation of Nondeterminisitc Data Types"
    [Nordic Journal of Computing, no. 2, 1995]
    [Tech. Rep. TUM-I9442, Inst. fur Informatik, Technische Universitat Munchen, 1994]
    • read the abstract
    • view the .ps file
    • ftp the .ps file

12. "Modeling partiality by nondeterminism"
    [Tech. Rep. 178, Department of Informatics, University of Bergen, 1999
    • view the .ps file

13. "Combining specification formalisms in the `general logic' of multialgebras", FLIRTS 2002 (2003)

14. "Composition and refinement of specifications of parameterized data types", REFINE 2002

15. Specification of Parameterized Programs - persistency revisited, Nordic Journal of Computing, 2001

    Logic

16. "On Specialization of Derivations in Axiomatic Equality Theories" [in Proc. of LFCS'94,LNCS vol. 813, 1994]

    Rewriting in multialgebras

17. "Reasoning and Rewriting with Set-Relations I: Ground Completeness"
    [Proc. of CSL'94, L.Pacholski, J.Tiuryn (eds.), LNCS vol. 933, 1995]
    • view the .ps file
    • a longer version with more proofs
    • ftp the .ps file

18. "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]
    • view the .ps file
    • ftp the .ps file

19. "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]
    • view the .ps file
    • ftp the .ps file

    Logic of multifunctions

    see "Multialgebras, Power Algebras and Complete Calculi of Identities and Inclusions" above

20. "A Complete Calculus for the Multialgebraic and Functional Semantics of Nondeterminism"
    [ACM TOPLAS, Vol. 17, No. 2, March 1995]
    • read the abstract
    • view the .ps file
    • ftp the .ps file

21. Quantifier-free logic for multialgebraic theories, WOLLIC, 2003 [revised version in Theoretical Computer Science, 2006]

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

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

23. "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

24. Bounded agents
    Strongly Complete Axiomatizations of ``Knowing At Most'' in Standard Syntactic Assignments, CLIMA'05.
    • Complete Axiomatization of Finite Syntactic Epistemic States, in Declarative Agent Languages and Technologies, workshop at AAMAS'2005.
    • "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)
    • "Developing Bounded Reasoning" (a preliminary version, 2008. The original publication is available at www.springerlink.com)

25. Complete axiomatisations of properties of finite sets, Logic Journal of the IGPL, vol.16, no.3, June 2008.

    Truth, graphs and paradox

26. Self-reference and paradoxes (infinitary theories and kernels of digraphs; later works on this list are with Sjur Dyrkolbotn)
    • "Self-reference, paradoxes and truth", [preprint] graph-based (or boolean equations based) approach to paradoxes of self-reference. All cases problematic for earlier approaches are solved in a simple way. (The publication from Synthese is available at www.springerlink.com or at JStore.)
    • "Paradoxes and kernels", Consistent propositional theories (possibly in infinitary logic) are equivalent to digraphs possessing kernels. The equivalence is exploited to establish some known and new results and to analyse particular theories.
    • "Finding kernels or solving SAT": analysing the relations between the algorithms for kernels and SAT, [Journal of Discrete Algorithms, vol.10, 146-164, 2012]
    • "Propositional Discourse Logic": graph structure of paradoxes, diagnosis of semantic paradoxes [preprint; to appear in Synthese]
    • "The holism of truth and paradox": with a complete diagnosis of semantic paradoxes using only classical logic

27. Argumenatation, paradox and kernels in directed graphs - a Ph.D. thesis by Sjur Dyrkolbotn, written (and defended) under my supervision in 2012.

28. Kernels of digraphs and satisfiability - some reverse mathematical results, at APAL, vol. 162, no. 3, March 2012
    

    Other things:

    1. philosophy, skiing.
    
    
    
    

    Miscellanous:

    You are the visitor number , since 17.10.2003. (The counter is due to the courtesy of http://www.digits.com.)