Forthcoming

• Szabolcs Mikulas, On representable ordered residuated semigroups.
  Submitted. 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, Axiomatizability of representable domain algebras.
  Submitted. 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. Springer, 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.
  
  
• 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.