2000

• E. Rosen and J. Tyszkiewicz. SO(∀∃*) sentences and their asymptotic probabilities. Mathematical Logic Quarterly, vol. 46, pp. 435–52, 2000.                                 
  Abstract   BibTeX

  We prove a 0-1 law for the fragment of second order logic SO(AE*) over parametric classes of structures which allow only one unary atomic type, confirming partially a conjecture of Lacoste. This completes the investigation of 0-1 laws for fragments of second order logic (with equality) defined in terms of first order quantifier prefixes over, e.g., simple graphs and tournaments. We also prove a low oscillation law, and establish the 0-1 law for $\Sigma\_1^4(\forall\exists^*)$ without any restriction on the number of unary types.

  @article{RoTy00,
       author = {Eric Rosen and Jurek Tyszkiewicz},
       journal = {Mathematical Logic Quarterly},
       pages = {435--52},
       title = {{{SO}$(\forall\exists^*)$ sentences and their asymptotic probabilities}},
       url = {http://www.logic.rwth-aachen.de/pub/rosen/ae.ps},
       volume = {46},
       year = {2000},
  }
  

1999

• F. Neven, M. Otto, J. Tyszkiewicz, and V. den Bussche. Adding FOR-Loops to First-Order Logic. In Proceedings of ICDT'99, vol. 1540 of LNCS, pp. 58–69. Springer, 1999.             
  BibTeX

  @inproceedings{NeOtTyVa99,
       author = {F. Neven and Martin Otto and Jurek Tyszkiewicz and Van den Bussche},
       booktitle = {{Proceedings of ICDT'99}},
       pages = {58--69},
       publisher = {{Springer}},
       series = {{LNCS}},
       title = {{Adding FOR-Loops to First-Order Logic}},
       volume = {1540},
       year = {1999},
  }
  

1998

• J. Tyszkiewicz. On the Kolmogorov Expressive Power of Boolean Query Languages. Theoretical Computer Science, vol. 190, pp. 317–361, 1998.                                 
  Abstract   BibTeX

  We address the question ''How much of the information stored in a given database can be retrieved by all Boolean queries in a given query language?'' In order to answer it we develop a Kolmogorov complexity based measure of expressive power of Boolean query languages over finite structures. This turns the above informal question into a precisely defined mathematical one. This notion gives a meaningful definition of the expressive power of a Boolean query language in a single finite database. \par The notion of Kolmogorov expressive power of a Boolean query language L in a finite database A is defined by considering two values: the Kolmogorov complexity of the isomorphism type of A, equal to the length of the shortest description of this type, and the number of bits of this description that can be reconstructed from truth values of all queries from L in A. The closer is the second value to the first, the more expressive is the query language. \par After giving the definitions and proving that they are correct, we concentrate our efforts on first order logic and its powerful extensions: inflationary fixpoint logic and partial fixpoint logic. We explore some connections between the proposed Kolmogorov expressive power of Boolean queries in these languages and their standard expressive power, in particular with the definability of order. We show that, except of being of interest for its own, our notion may have important diagnostic value for database query optimization.

  @article{Ty98,
       author = {Jurek Tyszkiewicz},
       journal = {Theoretical Computer Science},
       note = {See also: Proceedings of International Conference in Database Theory ICDT `95, Lecture Notes in Computer Science No. 893, Springer-Verlag 1995, 97--110.},
       pages = {317--361},
       title = {{On the Kolmogorov Expressive Power of Boolean Query Languages}},
       url = {http://www.logic.rwth-aachen.de/pub/jurek/kol.ps},
       volume = {190},
       year = {1998},
  }
  

1997

• P. Idziak and J. Tyszkiewicz. Monadic Second Order Probabilities in Algebra. Directly Representable Varieties and Groups. In Logic and Random Structures, AMS (R. B. Boppana and J. F. Lynch, Eds.), DIMACS Series in Discrete Mathematics and Theoretical Computer Science, AMS, pp. 79–108, 1997.             
  BibTeX

  @inproceedings{IdTy97,
       author = {P.~Idziak and Jurek Tyszkiewicz},
       booktitle = {{Logic and Random Structures, AMS}},
       editor = {R. B. Boppana and J. F. Lynch},
       pages = {79--108},
       series = {{DIMACS Series in Discrete Mathematics and Theoretical Computer Science, AMS}},
       title = {{Monadic Second Order Probabilities in Algebra. Directly Representable Varieties and Groups}},
       year = {1997},
  }
  

• J. Tyszkiewicz. The Kolmogorov Expression Complexity of Logics. Information and Computation, vol. 135, pp. 113–135, 1997.                                 
  Abstract   BibTeX

  The merit of the paper is to propose a completely new notion of complexity of logics in finite-model theory. It is the Kolmogorov variant of the Vardi's expression complexity. We define it by considering the value of the Kolmogorov complexity C(L[A]) of the infinite string L[A] of all truth values of sentences of L in A. The higher is this value, the more expressive is the logic L in A. \par If D is a class of finite models, then the value of C(L[A]) over all A in D is a measure of expressive power of L in D. Namely, unboundedness of C(L[A])-C(L'[A]) for A in D implies nonexistence of a recursive interpretation of L in L'. A version of this statement with complexities modulo oracle implies nonexistence of any interpretation of L in L'. Thus the values C(L[A]) modulo oracles constitute an invariant of expressive power of logics over finite models, depending on their real (absolute) expressive power, and not on the syntax. \par We investigate our notion for fragments of the infinitary logic L\_\ infty{\omega}^\omega: least fixpoint logic LFP and partial fixpoint logic PFP. We prove a precise characterization of 0-1 laws for these logics in terms of a certain boundedness condition placed on C(L[A]). We get an extension of the notion of a 0-1 law by imposing an upper bound on the value of C(L[A]) growing not too fast with cardinality of A, which still implies inexpressibility results similar to those implied by 0-1 laws.\par We also discuss the classes D in which C(PFPk[A]) is very high. It appears that then PFP or its simple extension can define all the PSPACE subsets of D.

  @article{Ty97,
       author = {Jurek Tyszkiewicz},
       journal = {Information and Computation},
       pages = {113--135},
       title = {{The Kolmogorov Expression Complexity of Logics}},
       url = {http://www.logic.rwth-aachen.de/pub/jurek/iandc.ps},
       volume = {135},
       year = {1997},
  }
  

• J. Tyszkiewicz. A Note on the Kolmogorov Data Complexity and Nonuniform Logical Definitions. Information Processing Letters, vol. 64, pp. 187–195, 1997.                                 
  Abstract   BibTeX

  We present a definition of the Kolmogorov data complexity and show how to use it to improve some already known results about hierarchies of Lindström quantifiers.

  @article{Ty97b,
       author = {Jurek Tyszkiewicz},
       journal = {Information Processing Letters},
       pages = {187--195},
       title = {{A Note on the Kolmogorov Data Complexity and Nonuniform Logical Definitions}},
       url = {http://www.logic.rwth-aachen.de/pub/jurek/kd.ps},
       volume = {64},
       year = {1997},
  }
  

• J. Tyszkiewicz. Queries and Algorithms Computable by Polynomial Time Existential Reflective Machines. Fundamenta Informaticae, vol. 32, pp. 91–105, 1997.                                 
  Abstract   BibTeX

  We consider two kinds of reflective relational machines: the usual ones, which use first order queries, and existential reflective machines, which use only first order existential queries. We compare these two computation models. We build on already existing results for standard relational machines, obtained by Abiteboul, Papadimitriou and Vianu, so we prove only results for existential machines. First we show that for both standard and existential reflective machines the set of polynomial time computable Boolean queries consists precisely of all PSPACE computable queries. \par The we go farther and compare which classes of algorithms both kinds of machines represent. \par It appears that, unless PSPACE=PTIME^NP, there are PSPACE queries which cannot be computed by polynomial time existential reflective machines which use only polynomial amount of relational memory, while it is always possible for standard reflective machines. We conclude that existential reflective machines, although equivalent in expressive power to unrestricted machines, provide substantially worse algorithms than the latter. \par On the positive side, we demonstrate that the above quality difference does not affect computing of PTIME queries, what can be done by existential reflective machines in PTIME, even if we take into account query evaluation costs, as well. \par Therefore within PTIME we use finer distinctions of the quality of algorithms. We demonstrate that any existential reflective machine computing the transitive closure query must use at least (1-o(1))log n variables, while for reflective relational machines using full first order queries already 3 variables suffice.

  @article{Ty97c,
       author = {Jurek Tyszkiewicz},
       journal = {Fundamenta Informaticae},
       pages = {91--105},
       title = {{Queries and Algorithms Computable by Polynomial Time Existential Reflective Machines}},
       url = {http://www.logic.rwth-aachen.de/pub/jurek/erm.ps},
       volume = {32},
       year = {1997},
  }
  

• J. Tyszkiewicz. Fine Hierarchies of Generic Computation. In Proceedings of International Conference in Database Theory ICDT `97 (F. Afrati and P. Kolaitis, Eds.), vol. 1186 of LNCS, pp. 125–139. Springer, 1997.                                 
  Abstract   BibTeX

  Suppose that you are a user of a commercial relational database, accessible over the Internet, whose owner has decided to copy the price lists of the US telephone companies – first order queries are for free just like local calls, because they are local by the theorem of Gaifman. All recursive queries, being potentially non-local, are charged, for simplicity let us assume \$ 1.00 for a Boolean query. Non-Boolean queries are certainly not allowed, because the user would require all the data to be sent to him by issuing the first order identity query, and then manipulate with it himself, without any pay. These are the rules. Well, what is your strategy, to compute all you want to know about the database, paying as little as possible? And how much will the total price be? \par We answer this question, showing that the question whether you can get your answer without any costs at depends on whether or not the theories of databases in the provided query language are finitely axiomatizable. \par Thus, assuming there is a limit on the number of variables allowed in queries, if the database query language is the fixpoint logic, you can get everything for free. When it is Datalog however, even with inequality and negation of the edb's, you have to pay. We present a method, which for graphs of $n$ vertices costs about \$ $log log n$. Thus querying a graph with 1 Terabyte vertices costs \$ 7.00. We demonstrate that this price cannot be substantially reduced without causing a large computational overhead.

  @inproceedings{Ty97d,
       author = {Jurek Tyszkiewicz},
       booktitle = {{Proceedings of International Conference in Database Theory ICDT `97}},
       editor = {F. Afrati and Ph. Kolaitis},
       pages = {125--139},
       publisher = {{Springer}},
       series = {{LNCS}},
       title = {{Fine Hierarchies of Generic Computation}},
       url = {http://www.logic.rwth-aachen.de/pub/jurek/fams.ps},
       volume = {1186},
       year = {1997},
  }
  

1995

• J. Tyszkiewicz. Probabilities in First-Order Logic of a Unary Function and a Binary Relation. Random Structures and Algorithms, vol. 6, pp. 181–191, 1995.                                 
  Abstract   BibTeX

  We settle the question of the behaviour of probabilities of sentences of first-order logic about a unary function and a binary relation. We show that there are sentences of this logic without asymptotic probability. \par This settles the last open case in the problem of establishing the behaviour of asymptotic probabilities for classes of labelled structures corresponding to natural signatures.

  @article{Ty95,
       author = {Jurek Tyszkiewicz},
       journal = {Random Structures and Algorithms},
       pages = {181--191},
       title = {{Probabilities in First-Order Logic of a Unary Function and a Binary Relation}},
       volume = {6},
       year = {1995},
  }
  

1994

• J. Tyszkiewicz. Infinitary queries and their asymptotic probabilities II: properties definable in least fixed point logic. Random Structures and Algorithms, vol. 5, pp. 215–234, 1994.                                 
  Abstract   BibTeX

  We develop an almost complete theory for existence of asymptotic probabilities of least fixed point and partial fixed point definable properties, and for the complexity of the associated almost sure theory. Our method works for any randomized class of finite structures.

  @article{Ty94,
       author = {Jurek Tyszkiewicz},
       journal = {Random Structures and Algorithms},
       pages = {215--234},
       title = {{Infinitary queries and their asymptotic probabilities II: properties definable in least fixed point logic}},
       url = {http://www.logic.rwth-aachen.de/pub/jurek/lfp.ps},
       volume = {5},
       year = {1994},
  }
  

1993

• J. Tyszkiewicz. On Asymptotic Probabilities in Logics That Capture DSPACE(log n) in Presence of Ordering. In Proceedings of TAPSOFT `93, vol. 668 of LNCS, pp. 569–583. Springer, 1993.                                 
  Abstract   BibTeX

  We show that for logics that capture DSPACE(log n) over ordered structures, and for recursive probability distributions on the class of finite models of the signature, the 0-1 law and the convergence law hold if and only if certain boundedness conditions are satisfied. As one of the applications, we solve the conjecture of Kolaitis and Vardi stating that for arbitrary probability distributions the 0-1 law holds for the logic L^\omega\_\infty{\omega} iff the same law holds for fixpoint logic.

  @inproceedings{Ty93b,
       author = {Jurek Tyszkiewicz},
       booktitle = {{Proceedings of TAPSOFT `93}},
       pages = {569--583},
       publisher = {{Springer}},
       series = {{LNCS}},
       title = {{On Asymptotic Probabilities in Logics That Capture DSPACE($\log n$) in Presence of Ordering}},
       url = {http://www.logic.rwth-aachen.de/pub/jurek/caap.ps},
       volume = {668},
       year = {1993},
  }
  

• J. Tyszkiewicz. On Asymptotic Probabilities of Monadic Second Order Properties. In Computer Science Logic, 6th Workshop, CSL `92, San Miniato 1992, Selected Papers (E. Börger, G. Jäger, H. K. Büning, S. Martini, and M. M. Richter, Eds.), vol. 702 of LNCS, pp. 425–439. Springer, 1993.                                 
  Abstract   BibTeX

  We propose a new, general and easy method for proving nonexistence of asymptotic probabilities of monadic second-order sentences in classes of finite structures where first-order extension axioms hold almost surely.

  @inproceedings{Ty93,
       author = {Jurek Tyszkiewicz},
       booktitle = {{Computer Science Logic, 6th Workshop, CSL `92, San Miniato 1992, Selected Papers}},
       editor = {E. B{\"o}rger and G. J{\"a}ger and H. Kleine B{\"u}ning and S. Martini and M. M. Richter},
       pages = {425--439},
       publisher = {{Springer}},
       series = {{LNCS}},
       title = {{On Asymptotic Probabilities of Monadic Second Order Properties}},
       url = {http://www.logic.rwth-aachen.de/pub/jurek/csl-mail.ps},
       volume = {702},
       year = {1993},
  }
  

1991

• J. Tyszkiewicz. Infinitary Queries and Their Asymptotic Probabilities I: Properties Definable in Transitive Closure Logic. In Proceedings of Workshop on Computer Science Logic CSL `91, vol. 626 of LNCS, pp. 396–410. Springer, 1991.                                 
  Abstract   BibTeX

  We present new general method for proving that for certain classes of finite structures the limit law fails for properties expressible in transitive closure logic. In all such cases also all associated asymptotic problems are undecidable.

  @inproceedings{Ty91,
       author = {Jurek Tyszkiewicz},
       booktitle = {{Proceedings of Workshop on Computer Science Logic CSL {`91}}},
       pages = {396--410},
       publisher = {{Springer}},
       series = {{LNCS}},
       title = {{Infinitary Queries and Their Asymptotic Probabilities I: Properties Definable in Transitive Closure Logic}},
       url = {http://www.logic.rwth-aachen.de/pub/jurek/tc.ps},
       volume = {626},
       year = {1991},
  }