
If you have any
difficulty to get the files or would
like to have the latest version, please drop me a line
at szabolcs@dcs.bbk.ac.uk.
Forthcoming
 Szabolcs Mikulas,
Ordered Monoids: Languages and Relations.
Submitted,
Preliminary version vailable as
pdf.
Abstract:
We give a finite axiomatization for
the variety generated by
relational, integral ordered monoids.
As a corollary we get a finite axiomatization for
the language interpretation as well.
 Brett McLean, Szabolcs Mikulas,
The Finite Representation Property for Composition, Intersection, Domain and Range.
International Journal of Algebra and Computation, accepted.
Preliminary version vailable on
arXiv.
Abstract:
We prove that the finite representation property holds for representation by partial functions
for the signature consisting of composition, intersection, domain and range and for any
expansion of this signature by the antidomain, fixset, preferential union, maximum iterate
and opposite operations. The proof shows that, for all these signatures, the size of base
required is bounded by a doubleexponential function of the size of the algebra.
This establishes that representability of finite algebras is decidable for all these signatures.
We also give an example of a signature for which the finite representation property
fails to hold for representation by partial functions.
 Tadeusz Litak, Szabolcs Mikulas and Jan Hidders,
Relational Lattices: From Databases to Universal Algebra.
Journal of Logical and Algebraic Methods in Programming, accepted.
Preliminary version vailable as
pdf.
Abstract: This is the journal version of Litak et al., RAMiCS 2014.
2016
 Robin Hirsch, Marcel Jackson and Szabolcs Mikulas,
The algebra of functions with antidomain and range.
Journal of Pure and Applied Algebra, 220(2016), no. 6, 22142239.
Preliminary version available as
pdf.
Abstract:
We give complete, finite quasiequational axiomatisations
for algebras of unary partial functions
under the operations of composition, domain, antidomain, range
and intersection.
This completes the extensive programme of classifying algebras
of unary partial functions under combinations of these operations.
We look at the complexity of the equational theories and provide a
nondeterministic polynomial upper bound.
Finally we look at the problem of finite representability and show that finite algebras
can be represented as a collection of unary functions over a finite base set
provided that intersection is not in the signature.
2015
 Szabolcs Mikulas,
The Equational Theories of Representable Residuated Semigroups.
Synthese, Volume 192, Issue 7 (2015), pp:21512158
,
http://link.springer.com/article/10.1007/s1122901405133
Preliminary version vailable as
pdf.
Abstract:
We show that the equational theory of representable lower
semilatticeordered residuated semigroups is finitely based. We survey
related results.
 Szabolcs Mikulas, Ildiko Sain, Andras Simon,
Complexity of equational theory of relational algebras with standard projection elements.
Synthese, Volume 192, Issue 7 (2015), pp.:21592182,
http://link.springer.com/article/10.1007/s1122901506891
Abstract:
The class TPA of true pairing algebras is defined to be the class of relation algebras
expanded with concrete set theoretical projection functions. The main results of the present paper
is that neither the equational theory of TPA nor the first order theory of TPA are decidable.
Moreover, we show that the set of all equations valid in TPA is exactly on the Pi^1_1 level.
We consider the class TPA of the relation algebra reducts of TPA’s, as well.
We prove that the equational theory of TPA is much simpler, namely, it is recursively enumerable.
We also give motivation for our results and some connections to related work.
 Szabolcs Mikulas,
Lower SemilatticeOrdered Residuated Semigroups and Substructural Logics.
Studia Logica(2015) 103: 453478,
http://link.springer.com/article/10.1007/s112250149574z
Preliminary version vailable as
pdf.
Abstract:
We look at lower semilatticeordered residuated semigroups and,
in particular, the representable ones, i.e.,
those that are isomorphic to algebras of binary relations.
We will evaluate expressions (terms, sequents, equations, quasiequations)
in representable algebras and give finite axiomatizations
for several notions of validity.
These results will be applied in the context of substructural logics.
2014
 Tadeusz Litak, Szabolcs Mikulas and Jan Hidders,
Relational Lattices.
in: P. Hoefner at al. (eds.), RAMiCS 2014, LNCS 8428, Springer,
pp. 327343, 2014.
Preliminary version vailable as
pdf.
Abstract:
Relational lattices are obtained by interpreting lattice connectives
as natural join and inner union between database relations.
Our study of their equational theory reveals that the variety generated
by relational lattices has not been discussed in the existing literature.
Furthermore, we show that addition of just the header constant to the
lattice signature leads to undecidability of the quasiequational theory.
Nevertheless, we also demonstrate that relational lattices are not as intangible
as one may fear: for example, they do form a pseudoelementary
class. We also apply the tools of Formal Concept Analysis and investigate
the structure of relational lattices via their standard contexts.
2013
 Philippe Balbiani and Szabolcs Mikulas,
Decidability and Complexity via Mosaics of the Temporal Logic
of the Lexicographic Products of Unbounded Dense Linear Orders.
In: Fontaine, Pascal; Ringeissen, Christophe; Schmidt, Renate (Eds.)
Frontiers of Combining Systems,
9th International Symposium, FroCoS 2013, Nancy, France, September 1820,
2013, Proceedings Series: Lecture Notes in Computer Science, Vol. 8152
Subseries: Lecture Notes in Artificial Intelligence, Springer, pp. 151164.
Preliminary version vailable as
pdf.
Abstract:
This article considers the temporal logic of the lexicographic
products of unbounded dense linear orders and provides via mosaics a
complete decision procedure in nondeterministic polynomial time for the
satisfiability problem it gives rise to.
 Robin Hirsch and Szabolcs Mikulas,
Ordered Domain Algebras.
Journal of Applied Logic, Volume 11 (2013), Issue 3, 266271.
Preliminary version vailable as
pdf.
Abstract:
We give a finite axiomatisation to representable ordered domain
algebras and show that finite algebras are representable on finite bases.
2012
 Ian Hodkinson and Szabolcs Mikulas,
On Canonicity and Completions of Weakly Representable Relation Algebras.
Journal of Symbolic Logic, Volume 77, Number 1, March 2012, 245262.
Preliminary version vailable as
pdf.
Abstract:
We show that the variety of weakly representable relation algebras is not closed
under canonical extensions.
 Hajnal Andreka, Szabolcs Mikulas and Istvan Nemeti,
Residuated Kleene Algebras. In:
R.L. Constable and A. Silva (Eds.), Kozen Festschrift,
LNCS 7230, pp. 111, SpringerVerlag, 2012.
Preliminary version vailable as
pdf.
Abstract:
We show that there is no finitely axiomatizable class of algebras
that would serve as an analogue to Kozen's class of Kleene algebras
if we include the residuals of composition in the similarity type of
relation algebras.
2011
 Hajnal Andreka, Szabolcs Mikulas and Istvan Nemeti,
The Equational Theory of Kleene Lattices.
Theoretical Computer Science 412(2011) 70997108,
doi:10.1016/j.tcs.2011.09.024;
presented as plenary talk at TACL 2011.
Preliminary version vailable as
pdf.
Abstract:
Languages and families of binary relations are standard
interpretations of Kleene algebras. It is known that the equational
theories of these interpretations coincide and that the free Kleene
algebra is representable both as a relational and as a language
algebra. We investigate the identities valid in these
interpretations when we expand the signature of Kleene algebras with
the meet operation. In both cases meet is interpreted as
intersection. We prove that in this case there are more identities
valid in language algebras than in relational algebras (exactly
three more in some sense), and representability of the free algebra
holds for the relational interpretation but fails for the language
interpretation. However, if we exclude the identity constant from
the algebras when we add meet, then the equational theories of the
relational and language interpretations remain the same, and the
free algebra is representable as a language algebra, too. The moral
is that only the identity constant behaves differently in the
language and the relational interpretations, and only meet makes this visible.
 Hajnal Andreka and Szabolcs Mikulas,
Axiomatizability of Positive Algebras of Binary Relations.
Algebra Universalis, Volume 66, Issue 1 (2011), Page 734,
DOI: 10.1007/s0001201101423.
Available:
preliminary version
and
errata.
Abstract:
We consider all positive fragments of Tarski's representable relation algebras
and determine whether the equational and quasiequational theories
of these fragments are finitely axiomatizable in firstorder logic.
We also look at extending the signature with reflexive, transitive closure and
the residuals of composition.
 Szabolcs Mikulas,
On representable ordered residuated semigroups.
Logic Journal of the IGPL (2011) 19(1): 233240,
first published online 17 December 2010,
doi: 10.1093/jigpal/jzq044
Preliminary version available as
pdf.
Abstract:
We show that the equational theory of representable
latticeordered residuated semigroups is not finitely
axiomatizable. We apply this result to the problem of
completeness of substructural logics.
 Robin Hirsch and Szabolcs Mikulas,
Positive Fragments of Relevance Logic and
Algebras of Binary Relations.
Review of Symbolic Logic,
volume 4, issue 01, pp. 81105.
Online version available
here,
(doi:10.1017/S1755020310000249, Cambridge University Press)
and
here.
Abstract:
We prove that algebras of binary relations
whose similarity type includes intersection,
union, and one of the residuals of relation composition
form a nonfinitely axiomatizable quasivariety and that
the equational theory is not finitely based.
We apply this result to the problem of the completeness
of the positive fragment of relevance logic
with respect to binary relations.
 Robin Hirsch and Szabolcs Mikulas,
Axiomatizability of representable domain algebras.
Journal of Logic and Algebraic Programming,
Volume 80, Issue 2, February 2011, Pages 7591.
Preliminary version available as
pdf.
Abstract:
The family of domain algebras provide an elegant formal system
for automated reasoning about programme verification.
Their primary models are algebras of relations, viz.
representable domain algebras.
We prove that, even for the minimal signature
consisting of the domain and composition operations,
the class of representable domain algebras is
not finitely axiomatizable.
Then we show similar results for extended
similarity types of domain algebras.
2009
 Hajnal Andreka, Szabolcs Mikulas,
The equational theory of representable ordered monoids.
Featured talk at TACL 2009.
Extended abstract and slides are available
here.

Tadeusz Litak, Jan Hidders and Szabolcs Mikulas,
Relational Lattices: An Introduction.
Talk at TACL 2009.
Extended abstract and slides are available
here
 Tim French, Szabolcs Mikulas, and Mark Reynolds,
A completeness proof for temporal epistemic logic
with perfect recall over linear time.
In C. Lutz and JF. Raskin (Eds.) Proceedings 16th International Symposium
on Temporal Representation and Reasoning (TIME2009),
BrixenBressanone, Italy 2325 July 2009, pp 8187. IEEE 2009.
Preliminary version available as pdf.
Abstract:
This paper presents various semantic interpretations for logics
of knowledge and time with prefect recall. We allow both past
and future operators
and examine the interpretation of different linear flows of time. In
particular, we present temporal epistemic logics for each of the
following flows of time: arbitrary linear orders; the integers;
the rationals; the reals; and for uniform flows of time. (By
uniform flows of time, we mean that time is an arbitrary linear
order that is common knowledge to all agents). We
propose axiomatizations for all logics except the last case, for
which we show that no finite axiomatization can be found. The
axiomatizations are shown to be sound and complete in the case of
arbitrary linear orders and the rationals.
 Szabolcs Mikulas,
Algebras of relations and relevance logic.
Journal of Logic and Computation,
19: 305321, 2009; doi:10.1093/logcom/exn099.
Preliminary version available as pdf.
Abstract: We prove that algebras of binary relations
whose similarity type includes intersection, composition, conversenegation and the identity constant
form a nonfinitely axiomatizable quasivariety,
and that the equational theory is not finitely based.
We apply this result to the problem of the completeness of relevant logic
with respect to binary relational semantics.
2007
 Robin Hirsch, Szabolcs Mikulas,
Representable semilatticeordered monoids.
Algebra Universalis, Vol. 57(3), pp:333370, 2007.
Paper available as pdf.
Abstract: We show that the quasivariety
of the {intersection, composition, identity}subreduct
of representable relation algebras is not finitely
axiomatizable.
2004
 Szabolcs Mikulas, Axiomatizability
of algebras of binary relations.
in Benedikt Loewe, Boris Piwinger, and Thoralf
Raesch, editors, Classical and New Paradigms
of Computation and their Complexity Hierarchies,
Papers of the conference "Foundations of the
Formal Sciences III" held in Vienna, September
2124, 2001, pp:187205. Kluwer, 2004,
Paper available as postscript.
Abstract: We present an overview
of the axiomatizability problem of algebras
of binary relations. The focus will be on the
finite and nonfinite axiomatizability of several
fragments of Tarski's class of representable
relation algebras. We examine the stepbystep
method for establishing finite axiomatizability
and ultraproduct constructions for establishing
nonfinite axiomatizability. We conclude with
some open problems that could be tackled using
either of the above methods.
2002
 Maarten Marx, Szabolcs Mikulas,
An elementary construction for a nonelementary
procedure.
Studia Logica, 72(2):253263, 2002.
Preliminary version available as postscript.
Abstract: We prove that bimodal
logics of products of Kripke frames satisfying
any combination of seriality, reflexivity and
symmetry have the product finite model property.
2001
 James Bailey and Szabolcs Mikulas,
Expressiveness issues and decision problems
for active database event queries.
In J. Van den Busche and V. Vianu, editors,
Database Theory  ICDT 2001, volume
1973 of Lecture Notes in Computer Science, pages
6882. SpringerVerlag, 2001.
Preliminary version available as postscript.
Abstract: A key facility of active
database management systems is their ability
to detect and react to the occurrence of events.
Such events can be either atomic in nature,
or specified using an event algebra to form
complex events. An important role of an event
algebra is to define the semantics of when events
become invalid (event consumption). In this
paper, we examine a simple event algebra and
provide a logical framework for specification
of various consumption policies. We then study
the problems of equivalence and implication,
identifying a powerful class of complex events
for which equivalence is decidable. We then
demonstrate how extensions of this class lead
to undecidability.
 Ivo Duentsch and Szabolcs Mikulas,
Cylindric structures and dependencies in relational
databases.
Theoretical Computer Science, 269(12):451468,
2001.
Preliminary version available as postscript.
Abstract: We explore the precise
connections between dependencies in relational
databases and variants of cylindric algebras.
We consider projectjoin dependencies and cylindric
dependencies and investigate the finite axiomatizability
of the corresponding classes of cylindric (semi)lattices.
 Ian Hodkinson, Szabolcs Mikulas,
and Yde Venema, Axiomatizing complex algebras
by games.
Algebra Universalis, 46:455478,
2001.
Preliminary version available as postscript.
Abstract: Given a variety V we
provide an axiomatization P(V) of the class
SCmV of complex algebras of algebras in V. P(V)
can be obtained effectively from the axiomatization
of V; in fact, if this axiomatization is recursively
enumerable, then P(V) is recursive.
 Maarten Marx, Szabolcs Mikulas,
Products, or how to create modal logics of high
complexity.
Logic Journal of the IGPL, 9:7788,
2001.
Available as postscript.
Abstract: We prove that the binary
product of the modal logic D is decidable. The
decision procedure is not elementary, and we
show that a small fragment of the languahe already
creates a highly complex satisfiability problem.
2000
 Ian Hodkinson
and Szabolcs Mikulas, Axiomatizability of reducts
of algebras of relations.
Algebra Universalis, 43:127156,
2000.
Preliminary version available as pdf.
Abstract: We show that generalized
subreducts of representable relation algebras
are not finitely axiomatizable if composition,
converse and intersection are definable. Similar
result is shown for fragments of representable
cylindric algebras if intersection and cylindrifications
are definable.
 Maarten Marx, Szabolcs Mikulas,
and Mark Reynolds, The mosaic method for temporal
logics.
In R. Dyckhoff, editor, Tableaux 2000,
Automated Reasoning with Analytic Tableaux and
Related Methods, volume 1847 of Lecture
Notes in Artificial Intelligence, pages 193214,
SpringerVerlag, 2000.
Preliminary version available as postscript.
Abstract: We apply the mosaic idea
to temporal logics to get easy proofs for completeness,
decidability and complexity. Furthermore, we
sketch how to implement the mosaic idea to design
a theoremprover for temporal logics.
 Maarten Marx, Szabolcs Mikulas,
and Stefan Schlobach, Labeled deduction for
the guarded fragment.
In D. Basin, M. D'Agostino, D.M. Gabbay, S.
Matthews, and L. Vigano, editors, Labeled
Deduction, pages 193214. Kluwer Academic
Publishers, 2000.
1999
 Robin Hirsch, Ian Hodkinson, Maarten
Marx, Szabolcs Mikulas, and Mark Reynolds, Mosaics
and stepbystep.
In E. Orlowska, editor, Logic at Work,
volume24 of Studies in Fuzziness and Soft Computing,
pages 158167. SpringerVerlag, 1999.
 Maarten Marx and Szabolcs Mikulas,
Decidability of cylindric set algebras of dimension
two and firstorder logic with two variables.
Journal of Symbolic Logic, 64(4):15631572,
1999.
 Maarten Marx, Szabolcs Mikulas,
and Stefan Schlobach, Tableau calculus for local
cubic modal logic and its implementation.
Logic Journal of the IGPL, 7/6:755778,
1999.
Available as postscript.
Abstract: A sound and complete
labelled tableau calculus is presented for twodimensional
modal logic interpreted on local squares. We
also give a short system description of the
Prolog theoremprover based on the calculus.
 Szabolcs Mikulas and Maarten Marx,
Undecidable relativizations of algebras of relations.
Journal of Symbolic Logic, 64:747760,
1999.
1998
 Hajnal Andreka, Steven Givant,
Szabolcs Mikulas, Istvan Nemeti, and Andras
Simon, Notions of rectangularity implying representability
in algebraic logic.
Annals of Pure and Applied Logic,
91:93190, 1998.
 Szabolcs Mikulas, Taming firstorder
logic.
Logic Journal of the IGPL 6/2:305316,
1998.
Available as postscript.
Abstract: Mosaic decidabilty proof
for relativized firstorder logic strengthened
by counting quantifiers.
1997
 Szabolcs Mikulas, A note on expressing
infinity in cylindricrelativized set algebras.
In Proceedings of ReLMiCS '97, Hammamet,
Tunisia, 1997.
1996
 Maarten Marx, Szabolcs Mikulas, Istvan Nemeti,
and Ildiko Sain, Investigations in arrow logic.
In M. Marx, L. Polos, and M. Masuch, editors,
Arrow Logic and Multimodal Logics,
Studies in Logic, Language and Information, pages
3562. CSLI Publications and FoLLI, 1996.
 Szabolcs Mikulas, Complete calculus for conjugated
arrow logic.
In M. Marx, L. Polos, and M. Masuch, editors,
Arrow Logic and Multimodal Logics,
Studies in Logic, Language and Information,
pages 125139. CSLI Publications and FoLLI,
1996.
Available as
pdf.
 Szabolcs Mikulas, Gabbaystyle calculi.
In H. Wansing, editor, Proof Theory of
Modal Logic, volume 2 of Applied Logic
Series, pages 243252. Kluwer Academic Publishers,
1996.
1995
 Hajnal Andreka, Valentin Goranko, Szabolcs Mikulas,
Istvan Nemeti, and Ildiko Sain, Effective temporal
logics of programs.
In L. Bolc and A. Szalas, editors, Time
and Logic, pages 51129. UCL Press, 1995.
 Maarten Marx, Szabolcs Mikulas, and Istvan
Nemeti, Taming logic.
Journal of Logic, Language and Information,
4:207226, 1995.
 Szabolcs Mikulas, Taming Logics.
PhD thesis, ILLC, University of Amsterdam, 1995.
 Szabolcs Mikulas, Istvan Nemeti, and Ildiko
Sain, Decidable logics of the dynamic trend
and relativized relation algebras.
In L. Csirmaz, D.M. Gabbay, and M. de Rijke,
editors, Logic Colloquium'92, Studies
in Logic, Language and Information, pages 165175.
CSLI Publications and FoLLI, 1995.
1994
 Hajnal Andreka and Szabolcs Mikulas, Lambek calculus
and its relational semantics: completeness and
incompleteness.
Journal of Logic, Language and Information,
3:137, 1994.
1993
 Szabolcs Mikulas, Strong completeness of the
Lambek calculus with respect to relational semantics.
In C. Rauszer, editor, Algebraic Methods
in Logic and in Computer Science, volume
28 of Banach Center Publications. Institute of
Mathematics, Polish Academy of Sciences, 1993.


