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):
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.
- Universal algebra and category theory:
Categories of multialgebras
Relational and power structures
Algebraic treatment of nondeterminism
INF-227 - Introduction to mathematical logic
INF-220 - Algebraic Specification:
- INF-121 (h-2005)
Files which are mentioned as available for ftp, can also be obtained directly by
anonymous ftp from the directory /pub/michal on the server ftp.ii.uib.no.
Multialgebraic semantics of nondeterminism
- "Algebraic Approaches to Nondeterminism - an Overview"
[ACM Computing Surveys,29, 1, March, 1997]
- "Generated Models and the Omega-rule: the Nondterministic Case"
[Proc. of TAPSOFT'95, LNCS, vol. 915, 1995]
- "Multialgebras, Power Algebras and Complete Calculi of Identities and Inclusions"
[ADT'94, in Recent Trends in Data Type Specification,LNCS, vol. 906, 1995]
- "Initiality + Nondeterminism => Junk"
[in Proc. of NIK'94,Tapir, 1994]
- "Singular and Plural Nondeterministic Parameters"
[SIAM Journal on Computing, 26-3, 1997 (1995)]
- "Nondeterminism vs. Underspecification", SCI 2001
- "The Institution of Multialgebras"
Tech.Rep. no.209, Department of Informatics, University of Bergen, 2000
More semantics (relations, multifunctions, universal algebra)
- "Relations, Multialgebras and Homomorphism"
- "The institution of Multialgebras - a general
framework for algebraic software development"
(a Ph.D. thesis written under my supervision by Yngve Lamo, 2003)
- "Computation Algebras"
[Tech. Rep. no. 117, Dept. of Informatics, University of Bergen, 1996]
Applications and extensions of nondeterministic specifications
- "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]
- "Modeling partiality by nondeterminism"
[Tech. Rep. 178, Department of Informatics, University of Bergen, 1999
- "Combining specification formalisms in the
`general logic' of multialgebras", FLIRTS 2002 (2003)
- "Composition and refinement of
specifications of parameterized data types", REFINE 2002
of Parameterized Programs - persistency revisited, Nordic Journal of
- "On Specialization of Derivations in Axiomatic Equality Theories"
[in Proc. of LFCS'94,LNCS vol. 813, 1994]
Rewriting in multialgebras
- "Reasoning and Rewriting with Set-Relations I: Ground Completeness"
[Proc. of CSL'94, L.Pacholski, J.Tiuryn (eds.), LNCS vol. 933, 1995]
- "Reasoning and Rewriting with Set-Relations II: Completeness for the
[Recent Trends in Data Type Specification, LNCS. vol.1130,
(eds. M.Haveraaen, O.Owe, O.-J.Dahl), Oslo, 1995]
- "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]
Logic of multifunctions
see "Multialgebras, Power Algebras and Complete Calculi of Identities and
- "A Complete Calculus for the
Multialgebraic and Functional Semantics of Nondeterminism"
[ACM TOPLAS, Vol. 17, No. 2, March 1995]
- Quantifier-free logic for multialgebraic
theories, WOLLIC, 2003 [revised version in Theoretical Computer Science, 2006]
Modal / Epistemic / Sequence logic / Bounded (finite) agents
- Sequence Logic
- "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
- Complete axiomatisations of properties of finite sets, Logic
Journal of the IGPL, vol.16, no.3, June 2008.
Truth, graphs and paradox
- 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
- Argumenatation, paradox and kernels in directed graphs - a Ph.D. thesis by Sjur Dyrkolbotn, written (and defended) under my supervision in 2012.
- Kernels of digraphs and satisfiability - some reverse mathematical results, at APAL, vol. 162, no. 3, March 2012
- philosophy, skiing.
You are the visitor number , since 17.10.2003. (The counter is due
to the courtesy of http://www.digits.com.)