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.

2019

• Marcel Jackson, Szabolcs Mikulas, Domain and range for angelic and demonic compositions. J. Log. Algebr. Meth. Program. 103: 62-78 (2019), Preliminary version vailable as pdf.
  Abstract: We give finite axiomatizations for the varieties generated by representable domain-range algebras when the semigroup operation is interpreted as angelic or demonic composition, respectively.

2016

• Tadeusz Litak, Szabolcs Mikulas and Jan Hidders, Relational Lattices: From Databases to Universal Algebra. Journal of Logical and Algebraic Methods in Programming, 85(4):540-573, 2016.
  Preliminary version vailable as pdf.
  Abstract: This is the journal version of Litak et al., RAMiCS 2014.
• Brett McLean, Szabolcs Mikulas, The Finite Representation Property for Composition, Intersection, Domain and Range. International Journal of Algebra and Computation, Vol. 26, No. 6 (2016) 1199-1215.
  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 double-exponential 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.
• 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, 2214-2239. 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:2151-2158 , http://link.springer.com/article/10.1007/s11229-014-0513-3
  Preliminary version vailable as pdf.
  Abstract: We show that the equational theory of representable lower semilattice-ordered 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.:2159-2182, http://link.springer.com/article/10.1007/s11229-015-0689-1
  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 Semilattice-Ordered Residuated Semigroups and Substructural Logics. Studia Logica(2015) 103: 453-478, http://link.springer.com/article/10.1007/s11225-014-9574-z
  Preliminary version vailable as pdf.
  Abstract: We look at lower semilattice-ordered 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, quasi-equations) 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. 327-343, 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 18-20, 2013, Proceedings Series: Lecture Notes in Computer Science, Vol. 8152 Subseries: Lecture Notes in Artificial Intelligence, Springer, pp. 151-164.
  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, 266-271.
  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, 245-262.
  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. 1-11, Springer-Verlag, 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) 7099-7108, 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 7-34, DOI: 10.1007/s00012-011-0142-3.
  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 first-order 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): 233-240, 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 lattice-ordered 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. 81-105.
  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 non-finitely 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 75-91.
  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 J-F. Raskin (Eds.) Proceedings 16th International Symposium on Temporal Representation and Reasoning (TIME-2009), Brixen-Bressanone, Italy 23-25 July 2009, pp 81--87. 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: 305-321, 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, converse-negation and the identity constant form a non-finitely 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 semilattice-ordered monoids.
  Algebra Universalis, Vol. 57(3), pp:333-370, 2007.
  Paper available as pdf.
  Abstract: We show that the quasi-variety 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 21-24, 2001, pp:187-205. 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 non-finite axiomatizability of several fragments of Tarski's class of representable relation algebras. We examine the step-by-step method for establishing finite axiomatizability and ultraproduct constructions for establishing non-finite axiomatizability. We conclude with some open problems that could be tackled using either of the above methods.

• Maarten Marx, Szabolcs Mikulas, An elementary construction for a non-elementary procedure.
  Studia Logica, 72(2):253-263, 2002.
  Preliminary version available as postscript.
  Abstract: We prove that bi-modal logics of products of Kripke frames satisfying any combination of seriality, reflexivity and symmetry have the product finite model property.

• 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 68-82. Springer-Verlag, 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(1-2):451-468, 2001.
  Preliminary version available as postscript.
  Abstract: We explore the precise connections between dependencies in relational databases and variants of cylindric algebras. We consider project-join 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:455-478, 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:77-88, 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.

• Ian Hodkinson and Szabolcs Mikulas, Axiomatizability of reducts of algebras of relations.
  Algebra Universalis, 43:127-156, 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 193-214, Springer-Verlag, 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 theorem-prover 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 193-214. Kluwer Academic Publishers, 2000.

• Robin Hirsch, Ian Hodkinson, Maarten Marx, Szabolcs Mikulas, and Mark Reynolds, Mosaics and step-by-step.
  In E. Orlowska, editor, Logic at Work, volume24 of Studies in Fuzziness and Soft Computing, pages 158-167. Springer-Verlag, 1999.
  
  
• Maarten Marx and Szabolcs Mikulas, Decidability of cylindric set algebras of dimension two and first-order logic with two variables.
  Journal of Symbolic Logic, 64(4):1563-1572, 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:755-778, 1999.
  Available as postscript.
  Abstract: A sound and complete labelled tableau calculus is presented for two-dimensional modal logic interpreted on local squares. We also give a short system description of the Prolog theorem-prover based on the calculus.
  
  
• Szabolcs Mikulas and Maarten Marx, Undecidable relativizations of algebras of relations.
  Journal of Symbolic Logic, 64:747-760, 1999.

• 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:93-190, 1998.
  
  
• Szabolcs Mikulas, Taming first-order logic.
  Logic Journal of the IGPL 6/2:305-316, 1998.
  Available as postscript.
  Abstract: Mosaic decidabilty proof for relativized first-order logic strengthened by counting quantifiers.

1997

• Szabolcs Mikulas, A note on expressing infinity in cylindric-relativized 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 35-62. 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 125-139. CSLI Publications and FoLLI, 1996.
  Available as pdf.
  
  
• Szabolcs Mikulas, Gabbay-style calculi.
  In H. Wansing, editor, Proof Theory of Modal Logic, volume 2 of Applied Logic Series, pages 243-252. 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 51-129. UCL Press, 1995.
  
  
• Maarten Marx, Szabolcs Mikulas, and Istvan Nemeti, Taming logic.
  Journal of Logic, Language and Information, 4:207-226, 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 165-175. 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:1--37, 1994.

• 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.