Mon 29 Jan, 2007


Steel: Models derived from mice, preliminary draft. pdf.
---

Welch:
new:
new: Arithmetical quasi-inductive definitions and the transfinite action of 1-tape
new: Turing machines
new: submitted dvi%endtag pdf%endtag


Sun 28 Jan, 2007


McColm:
deleted: deleted: content="My mathematical research program, vitae, and .ps
deleted: copies of recent papers.">
deleted: deleted: content="mathematical games, positive elementary induction,
deleted: least fixed points, eventual periodicity,
deleted: dimension, arity, pebble games, zero-one laws,
deleted: threshold functions"> deleted: Mathematical Research href="http://www.math.usf.edu/~mccolm/research/games/RGintro.html">mat hematical games and
deleted: random structures.
deleted: I have some pages for logical and combinatorial games linked from this
deleted: page, and I will be putting up some stuff on random structures in the
deleted: foreseeable future.
deleted: The most of this page is devoted to past papers.
deleted: I am trying to understand mathematical games --- i.e., those things known
deleted: as "mathematical games" by logicians and combinatorists, and as "extended
deleted: games" by game theorists.
deleted: So what I am doing in this web-site is describing some important research
deleted: (including my own) with references for people who want to explore further.
deleted: Since I am trying to learn something about these subjects, I appreciate
deleted: questions, comments, and even (gentle) criticism.
deleted: I especially appreciate new kinds of games and new models of random
deleted: structures, and other areas of game theory that I have missed.
deleted: Perhaps I should explain where I am coming from.
deleted: I got a Ph.D. in mathematics from UCLA in 1986, where I had worked on
deleted: abstract recursion under Yiannis Moschovakis.
deleted: (The kind of abstract recursion I worked on was elementary induction, which
deleted: is now called Least Fixed Point logic, or just LFP to very theoretical
deleted: computer scientists.)
deleted: Most of my thesis was on recursion on infinite models, but I soon was
deleted: doing work on finite models.
deleted: I also spent some time working on ramsey theory, and also in analysis.
deleted: More recently, I became convinced that pebble games were the
to
deleted: understanding LFP.
deleted: I do not mean the pebble games developed by Ehrenfeucht, I mean the more
deleted: ancient game of the sort: you have a statement P and a structure M, and
deleted: there are two players, call them Eloise and Abelard (some people call them
deleted: I and II, or Angel and Demon, or Assertor and Denier).
deleted: They play a game on M in such a way that Eloise has a winning strategy iff
deleted: P is true on M.
deleted: For example, if M was a graph, and P was the statement "the graph is
deleted: connected", then the game would be as follows.
deleted: First, Abelard chooses two vertices, a and b.
deleted: Then Eloise must choose a sequence of vertices x(1), x(2), ..., x(n) so
deleted: 1. a = x(1) and x(n) = b.
deleted: 2. For each i, 0 < i < n, there is an edge from x(i) to x(i+1).
deleted: If Eloise succeeds, she wins.
deleted: If Eloise never succeeds, Abelard wins (so it could take an infinite amount
deleted: of time for Eloise to lose, if she simply wanders around forever.
deleted: In this game, if M is a connected graph, then Eloise has a winning
deleted: strategy: she can just select the vertices of some path from a to b in
deleted: sequence.
deleted: On the other hand, if M is not connected, then Abelard could select a and
deleted: b on separate components, and then sit back and watch Eloise fail to
deleted: select a path connecting them.
deleted: So that is where I am at present.
deleted: To go to my first game page, click here.
deleted: The rest of this page consists of links and references to my papers. Papers deleted: deleted: Here are papers that have already appeared in journals. deleted:
deleted: 1. Some restrictions on simple fixed points of the integers,
deleted: J. Sym. Logic 54:4 (1989), 1324-1345.
deleted: This is the first half of my Ph.D. thesis.
deleted: Its about abstract recursion on the natural numbers with successor,
deleted: predecessor, and 0.
deleted: We find some restrictions on simple (i.e., without parallelism) fixed
deleted: points.
deleted: Out of this somewhat esoteric acorn, eventual periodicity (5. below) would
deleted: grow.
deleted: 2. Parametrization over inductions with a bounded number of variables,
deleted: Ann. Pure & Appl. Logic 48 (1990), 103-134.
deleted: This is the third fourth of my Ph.D. thesis.
deleted: Here, we generalize the classical parametrization theorems to non-acceptable
deleted: structures (which include the finite structures).
deleted: The discerning reader will detect the blooper on p. 124.
deleted: 3. When is Arithmetic Possible?,
deleted: Ann. Pure & Appl. Logic 50 (1990), 129-151.
deleted: The last fourth of my Ph.D. thesis.
deleted: Here I launch two conjectures on LFP logic: on a class of
deleted: (finite) structures, FO = LFP iff all LFP inductions are bounded, and
deleted: all LFP inductions are bounded iff the a popular infinitary logic
deleted: collapses to FO.
deleted: Kolaitis, Vardi and Dewar confirmed the latter conjecture, while
deleted: Immerman, Gurevich and Shelah found counterexamples to the former.
deleted: 4. A Ramseyian Theorem for Products of Trees,
deleted: J. Comb. Th.-A 57:1 (1991), 68-75.
deleted: Suppose that P is a Cartesian product of posets.
deleted: Let X be a coloring of P: for each tuple p, X(p) is a color in I.
deleted: Under what conditions do we know that there must be a color i such
deleted: that there is an i-colored copy of one of the poset factors of P?
deleted: We explore the situation for I finite and each factor being a finitary
deleted: tree: such an i must exist.
deleted: There is a counterexample when non-finitary trees are allowed.
deleted: We conjecture that when I and all factors are finite, such i must exist.
deleted: 5. Eventual Periodicity and One-Dimensional Queries,
deleted: Notre Dame J. Formal Logic 33:2 (1992), 273-290.
deleted: Out of the esoteric acorn (see [1], above) comes: on large, chain-like
deleted: graphs, one-dimensional and monadic second order-definable relations
deleted: are `eventually periodic' in the sense that they eventually cycle on
deleted: the chains in a predictable way.
deleted: We can take advantage of the monotonicity of LFP inductions to separate
deleted: some expressibility classes, in particular, separating 1-dimensional
deleted: LFP from Monadic Second Order (as described by Buchi & Ladner).
deleted: 6. On the complexity of deadlock-free programs on a ring of processors
deleted: (with W. E. Clark &
deleted: W. R. Stark, both at USF),
deleted: J. Par. Dist. Comp. 16 (1992), 67-71.
deleted: This is a cute application of extremal graph theory to parallel computing.
deleted: We have a ring of processors, each communicating to its `predecessor'
deleted: each having an identical incomplete program.
deleted: We want to know how complete the programs must be to assure that the
deleted: system won't be unable to act.
deleted: 7. Some Ramsey theory in boolean algebra for complexity classes,
deleted: Z. math. Logik Grund. Math. 38 (1992), 293-298.
deleted: We take a bit of lore, the fact that for any countable W, if A and B are
deleted: subsets of W, then there exists an infinite subset H of W such that
deleted: the intersections of A and H and of A and B are the same.
deleted: We see how far we can push this result, and look at applications in
deleted: expressibility theory.
deleted: 8. Dimension Versus Number of Variables, and Connectivity, Too,
deleted: Math. Log. Quart. 41 (1995), 111-134.
deleted: Dimension and Number of variables are two complexity measures in LFP
deleted: logic.
deleted: We look at the game-theoretic version of LFP explored in paper [11]
deleted: below, and represent dimension and number of variables.
deleted: We use these characterizations to compute the dimension and number
deleted: of variables of nonconnectivity.
deleted: 9. On the Power of Deterministic Transitive Closure
deleted: (with
deleted: E. Graedel, at the Lehrgebiet Mathematische Grundlagen der
deleted: Informatik, in Aachen),
deleted: Inform. & Comp. 119:1 (1995), 129-135.
deleted: We prove that FO + pos DTC is closed under negation, and within
deleted: some highly uniform graphs collapses into FO, thus separating it
deleted: from FO + pos TC.
deleted: This paper follows a LICS abstract.
deleted: 10. The Dimension of the Negation of Transitive Closure,
deleted: J. Sym. Logic 60:2 (1995), 392-413.
deleted: The long-awaited horrible proof (using eventual periodicity and
deleted: monotonicity) that non-reachability on finite
deleted: graphs is precisely 2-dimensional.
deleted: Remember, you heard it here first.
deleted: 11. Pebble games and subroutines in least simple fixed point logic,
deleted: Inform. & Comp. 122:2 (1995), 201-220.
deleted: Here, I generalize LFP into a Datalog-like game structure, which allows
deleted: me to generate a nonlinear hierarchy in stratified least fixed point
deleted: logic, based on subroutines.
deleted: This is is continued in [8] above, and is the basis for much of my current
deleted: research.
deleted: Incidentally, I have since discovered that a more general investigation
deleted: anticipating some of my approach was launched decades ago by
deleted: see my page on Game
deleted: Theoretic Semantics for details.
deleted: 12. Hierarchies in Transitive Closure Logic, Stratified Datalog,
deleted: and Infinitary Logic,
deleted: (with
deleted: E. Graedel, at the Lehrgebiet Mathematische Grundlagen der
deleted: Informatik, in Aachen),
deleted: Ann. Pure & Appl. Logic 77 (1996), 169-199.
deleted: We prove that non-reachability is not in FO + pos TC.
deleted: We cook up an alternate hierarchy to the one in [11], and present a proof
deleted: of (a a stronger version of) the Main Theorem of [11].
deleted: This paper follows a FOCS abstract.
deleted: 13. An application of spanning trees to the separation of $k$ points
deleted: in Euclidean space,
deleted: (with B. Shekhtman and
deleted: W. E. Clark,
deleted: at USF), Proc. Lond Math. Soc. (2) 58 (1998), 297-130.
deleted: In n-space, say that a set F of functions from n-space to the reals is
deleted: k-separating if, for every k-subset S of n-space, there is a function f in
deleted: F that is 1-1 on S.
deleted: We prove that the minimum k-separating sets of differentiable functions
deleted: have n(k - 1) functions.
deleted: 14. A Splitting Inequality,
deleted: Ramanujan 2 (1998), 511-519.
deleted: We present a new (and at last, completely elementary) proof of the
deleted: theorem that all monotone-increasing properties of graphs have
deleted: weak thresholds.
deleted: We explore the connection between this proof and the Bollobas-Thomason
deleted: proof, which uses the Kruskal-Katona theorem.
deleted: The relation to the S-shaped theorem of reliability theory is investigated
deleted: in the paper on weak thresholds above.
deleted: 15. First Order Zero One Laws for Random Graphs on the Circle,
deleted: Random Struct. & Alg. 14 (1999) 239-266. scatter
deleted: n vertices on a metric space and connect those which are within
deleted: distance d apart.
deleted: This model has been investigated, overtly or otherwise, in the theory
deleted: of coverage processes, percolation, cluster analysis, biological
deleted: models of computation, and elsewhere.
deleted: We have the metric space be the unit circle (the distance being measured
deleted: around the circle), and we look at what happens as d = d(n)
deleted: rises from 0 to pi.
deleted: (Some of these results were anticipated in a more precise paper by
deleted: E. Godehardt and J. Jaworsky, On the connectivity of a random interval
deleted: graph, in
deleted: Random Structures & Algorithms 9:2, 1996, and apparently not reviewed
deleted: in the AMS Reviews, grump, grump, grump, so let's say that the AMS Review
deleted: should say that if you want to understand this model, start with this
deleted: paper.)
deleted: Among other things, we find that for each fixed d, the set of
deleted: a.s. FO sentences in this model is a complete noncategorical theory.
deleted: This paper follows a LICS abstract.
deleted: 16. MSO Zero One Laws on Random Labelled Acyclic Graphs,
deleted: Discrete Mathematics 254 (2002) 331-347.
deleted: We prove a result announced in the AMS abstracts.
deleted: We use elementary methods to prove that over free labelled trees, MSO
deleted: definable queries are almost surely true or almost surely false.
deleted: 17. Introducting Random Trees, Research on
deleted: Language and Computation 1 (2003), 203-226.
deleted: This is an introduction to random trees intended for non-experts (i.e.,
deleted: researchers with no particular background in probabilistic methods or
deleted: in combinatorics).
deleted: We describe three useful techniques --- moment methods, generating functions,
deleted: and branching processes.
deleted: We also give some background and applications to computation.
deleted: 18. An Anti-Ramsey Theorem on Posets,
deleted: Bulletin of the Institute of Combinatorics and its Applications 38
deleted: (2003) 84-100.
deleted: After my paper on A Ramseyian Theorem for Products of Trees, I
deleted: conjectured that any 2-coloring (i.e., red & blue) of a Cartesian product
deleted: of finite posets P x Q admits either a red copy of P or a blue copy of Q.
deleted: In this paper, I disprove this conjecture by proving that if n is sufficiently
deleted: larger than m, then there is a 2-coloring of the poset of the power set
deleted: of [m+n] that does not admit either a red copy of the poset of the power
deleted: set of [n], nor a blue copy of the poset of the power set of [2].
deleted: 19. Guarded Quantification in Least Fixed Point Logic,
deleted: J. Logic, Language and Information, to appear.
deleted: This article introduces a (positive) least fixed point logic in which
deleted: quantification is restricted by guard relations.
deleted: This logic is more relaxed than previous guarded least fixed point logics,
deleted: which were motivated by modal logic type considerations: this one was
deleted: motivated by game logic and database considerations.
deleted: This logic turns out to have the same expressive power as the classical
deleted: positive least fixed point logic of Moschovakis.
deleted: 20. On the Structure of Random Unlabelled Acyclic
deleted: Graphs, Discrete Mathematics 227 (2004), 147 - 170.
deleted: We use prove a variation of a result of
deleted: Alan Woods
deleted: (that all MSO queries over random trees have asymptotic probabilities, see
deleted: RSA 10 (1997) Colouring rules for finite trees ...) that over free
deleted: unlabelled trees, MSO definable queries are almost surely true or
deleted: almost surely false.
deleted: The proof is an elementary version of Woods's approach, and this
deleted: scenic route gives us a lot of information about the anatomy of
deleted: (almost all) unlabelled trees.
deleted: 21. Threshold Functions for Random Graphs on a Line
deleted: Segment, Combinatorics, Probability, Computing 13 (2004), 373 - 387.
deleted: This article presents a proof that in the 1-dimensional model of Gilbert
deleted: random graphs, all upwards closed properties have at least weak thresholds.
deleted: In addition, all upwards closed properties whose thresholds are sufficiently
deleted: higher than the threshold for connectivity have strong thresholds.
deleted: We also present some counterexamples.
deleted: I have just seen an interesting paper on a variant of these problems
deleted: for higher dimensions by
deleted:
deleted: Ashish Goel, Bhaskar Krishnamacari, and Sanatan Rai; they use
deleted: matching methods which, alas, will suffice for the not-so-sparse
deleted: strong threshold results but not for the just-above-phase-transition
deleted: weak threshold results. deleted: Other stuff: comments are appreciated. deleted: Inductive Norms and Negation, in preparation.
deleted: This is the first of a series of articles on fragments of Least Fixed
deleted: Point logic, with restrictions imposed on quantifications.
deleted: This paper introduces generalizations of the Moschovakis Boundedness
deleted: Theorem and the Immerman Negation of LFP Theorem, and explores the
deleted: sharpness of the latter using the logic "positively stratified
deleted: Existential Fixed Point."
deleted: Game Representations of Complexity Classes,
deleted: presented to the European Summer School on Logic, Language and Information,
deleted: 2001, at Helsinki.
deleted: This extends [11] above with game representations of NLOGSPACE (FO + pos TC),
deleted: PSPACE, and EXPTIME; these representations can be extended to higher types. Escape links
deleted: Back to my home page
deleted: Back to the USF Department of Mathematics
deleted: Home Page


Fri 19 Jan, 2007


Kechris:
new: Unitary representations and modular actions, Journal of Math. Sciences, 140(3)
new: (2007), 398-425.
--- Representation
deleted: Theory, Dynamical Systems, Combinatorial and Algorithmic Methods. Part
deleted: 13, Ed. A. A. Lodkin, Zapiski Nauchnyh Seminarov POMI, 326
deleted: (2005), 97-144. Reprinted in: Journal of Math. Sciences, 140(3)
deleted: (2007), 398-425.
deleted: Click here for the .ps file
deleted: or .pdf file of this paper


Wed 17 Jan, 2007


Eklof:
new: ^-TN as an abstract elementary class (with J. Baldwin and J. Trlifaj), preprint
---
deleted: perp N as an abstract elementary class (with J. Baldwin and J. Trlifaj), preprint
new: Shelah's Singular Compactness Theorem, CRM Preprint Series
---
deleted: Shelahs Singular Compactness Theorem, CRM Preprint Series

Hirschorn:
---
--- REFRESH(4 sec): http://homepage.univie.ac.at/James.Hirschorn/research/research.html
--- This web page has been moved he re.
--- Publication List
deleted: Please click on a link below for more information on any of these articles. Publications 1. James Hirschorn, Some partition properties for measurable colourings of w*₁², Suuri kaiseki kenkyuusho koukyuuroku 1423 (2005), 28-52. 2. James Hirschorn, Measure Theory, Chapters K3 and K4 of The Encyclopedia of General Topology, (pp. 459-469), Elsevier Science Publishers, Amsterdam, 2004. 3. James Hirschorn, Random gaps under CH, Transactions of the American Mathematical Society 356 (2004), no. 4, 1281-1290. 4. James Hirschorn, Summable gaps, Annals of Pure and Applied Logic 120 (2003), no. 1-3, 1-63. 5. James Hirschorn, Towers of measurable functions, Fundamenta Mathematicae 164 (2000), no. 2, 165-192. 6. James Hirschorn, Towers of Borel functions, Proceedings of the American Mathematical Society 128 (2000), no. 2, 599-604. Preprints 7. James Hirschorn, Partial order embeddings with convex range, (version: 02.01.2007, subject: Order Theory, Ordered Algebra). 8. James Hirschorn, Pinning quasi orders with their endomorphisms, (version: 03.10.2006, subject: Order Theory). 9. James Hirschorn, Random gaps, 2006, to appear in Transactions of the American Mathematical Society. 10. James Hirschorn, On the strength of Hausdorff's gap condition, 2002, to appear in Fundamenta Mathematicae. 11. James Hirschorn, Random trees under CH, 2000, to appear in Israel Journal of Mathematics. 12. Thesis * James Hirschorn, Cohen and random reals, Ph.D. thesis, University of Toronto, 2000.


Tue 16 Jan, 2007


Hirschorn:
--- Publication List
new: Please click on a link below for more information on any of these articles. Publications 1. James Hirschorn, Some partition properties for measurable colourings of Ï₁², Suuri kaiseki kenkyuusho koukyuuroku 1423 (2005), 28â52. 2. James Hirschorn, Measure Theory, Chapters K3 and K4 of The Encyclopedia of General Topology, (pp. 459â469), Elsevier Science Publishers, Amsterdam, 2004. 3. James Hirschorn, Random gaps under CH, Transactions of the American Mathematical Society 356 (2004), no. 4, 1281â1290. 4. James Hirschorn, Summable gaps, Annals of Pure and Applied Logic 120 (2003), no. 1â3, 1â63. 5. James Hirschorn, Towers of measurable functions, Fundamenta Mathematicae 164 (2000), no. 2, 165â192. 6. James Hirschorn, Towers of Borel functions, Proceedings of the American Mathematical Society 128 (2000), no. 2, 599â604. Preprints
--- Publication List
deleted: Please click on a link below for more information on any of these articles. Publications 1. James Hirschorn, Some partition properties for measurable colourings of w*₁², Suuri kaiseki kenkyuusho koukyuuroku 1423 (2005), 28â52. 2. James Hirschorn, deleted: Measure Theory, Chapters K3 and K4 of deleted: The Encyclopedia of General Topology, (pp. 459â469), Elsevier Science Publishers, Amsterdam, 2004. 3. James Hirschorn, Random gaps under CH, Transactions of the American Mathematical Society 356 (2004), no. 4, 1281â1290. 4. James Hirschorn, Summable gaps, deleted: Annals of Pure and Applied Logic 120 (2003), no. 1â3, 1â63. 5. James Hirschorn, deleted: Towers of measurable functions, deleted: Fundamenta Mathematicae 164 (2000), no. 2, 165â192. 6. James Hirschorn, deleted: Towers of Borel functions, deleted: Proceedings of the American Mathematical Society 128 (2000), no. 2, 599â604. Preprints James Hirschorn, Partial order embeddings with convex range, (version: 02.01.2007, subject: Order Theory, Ordered Algebra). James Hirschorn, Pinning quasi orders with their endomorphisms, (version: 03.10.2006, subject: Order Theory). James Hirschorn, Random gaps, 2006, to appear in Transactions of the American Mathematical Society. James Hirschorn, On the strength of Hausdorff's gap condition, 2002, to appear in Fundamenta Mathematicae. James Hirschorn, Random trees under CH, 2000, to appear in Israel Journal of Mathematics.
--- James Hirschorn, Random gaps, 2006, to appear in Transactions of the American Mathematical Society. James Hirschorn,
deleted: On the strength of Hausdorff's gap condition, 2002, to appear in Fundamenta Mathematicae. James Hirschorn,
deleted: Random trees under CH, 2000, to appear in Israel Journal of Mathematics. James Hirschorn, Pinning quasi orders with their endomorphisms, (version: 03.10.2006, subject: Order Theory). Thesis * James Hirschorn, Cohen and random reals, Ph.D. thesis, University of Toronto, 2000.
--- Thesis * James Hirschorn, deleted: Cohen and random reals, deleted: Ph.D. thesis, University of Toronto, 2000.

Leshem:
---
deleted: [an error occurred while processing this directive]


Sun 14 Jan, 2007


Schindler:
new: Version vom 10.01.07 (Kapitel 1-9):
---
deleted: Version vom 08.12.06 (Kapitel 1-9):


Sat 13 Jan, 2007


Cameron: Probability% endtag% Notes on Complexity
--- Probability Notes on Complexity Notes on counting Introducti on to Algebra
--- Notes on counting
new: 12 January 2007
---
deleted: 21 December 2006

Eklof: open_update.pd f
--- open_update.p df
new: perp N as an abstract elementary class (with J. Baldwin and J. Trlifaj), preprint Nperp-aec.pdf%en dtag%
new: Shelahs Singular Compactness Theorem, CRM Preprint Series SingComp.pdf%endt ag%

Hirschorn: James Hirschorn, Pinning quasi orders with their endomorphisms, (version: 03.10.2006, subject: Order Theory).
---


Wed 10 Jan, 2007


Schindler:
new: (2006),
---
deleted: (2004), Kurt Gödel (1906-1878), DMV-Nachrichten 14 (2006), pp. 42 - 45;
new: English translation: Newsletter of the European Math. Society
new: 62 (2006), pp. 29 - 31.
--- Kurt Gödel (1906-1878), DMV-Nachrichten 14 (2006), pp. 42 - 45. Hausdorff Center for Math, Bonn, Jan 23, 07, The P vs.
new: NP problem for infinite time Turing machines


Fri 5 Jan, 2007


Thomas:
new: unpublished preprint, April 2002.
---
deleted: preprint, April 2002.
new: Equivalence Relations submitted December 2006.
---
deleted: Equivalence Relations revised version, December 2006.

Truss:
new: University of Leeds preprint, 18, 2005, to appear in the Journal of
new: Symbolic Logic.
---
deleted: University of Leeds preprint, 18, 2005.
new: Last changed 4-1-2007.
---
deleted: Last changed 21-11-2006.

Welch:
new: ``Games for supervaluation and dependency''.pdf
new:
new: Kolkata Meeting 5'th January 2007
new: "Games and Abstract Inductive Definitions" deleted: ``Games for supervaluation and dependency''.pdf