34 found
Sort by:
Disambiguations:
André Nies [34]Andreé Nies [2]
  1. Laurent Bienvenu, Rupert Hölzl, Joseph S. Miller & André Nies (forthcoming). Denjoy, Demuth, and Density. Journal of Mathematical Logic:140318013417000.
    Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
  2. George Barmpalias, Vasco Brattka, Adam Day, Rod Downey, John Hitchcock, Michal Koucký, Andy Lewis, Jack Lutz, André Nies & Alexander Shen (2013). Isaac Newton Institute, Cambridge, UK July 2–6, 2012. Bulletin of Symbolic Logic 19 (1).
    Direct download  
     
    My bibliography  
     
    Export citation  
  3. André Nies (2012). Computably Enumerable Sets Below Random Sets. Annals of Pure and Applied Logic 163 (11):1596-1610.
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  4. George Barmpalias & André Nies (2011). Upper Bounds on Ideals in the Computably Enumerable Turing Degrees. Annals of Pure and Applied Logic 162 (6):465-473.
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  5. Noam Greenberg & André Nies (2011). Benign Cost Functions and Lowness Properties. Journal of Symbolic Logic 76 (1):289 - 312.
    We show that the class of strongly jump-traceable c.e. sets can be characterised as those which have sufficiently slow enumerations so they obey a class of well-behaved cost functions, called benign. This characterisation implies the containment of the class of strongly jump-traceable c.e. Turing degrees in a number of lowness classes, in particular the classes of the degrees which lie below incomplete random degrees, indeed all LR-hard random degrees, and all ω-c.e. random degrees. The last result implies recent results of (...)
    Direct download (5 more)  
     
    My bibliography  
     
    Export citation  
  6. Greg Hjorth & André Nies (2011). Borel Structures and Borel Theories. Journal of Symbolic Logic 76 (2):461 - 476.
    We show that there is a complete, consistent Borel theory which has no "Borel model" in the following strong sense: There is no structure satisfying the theory for which the elements of the structure are equivalence classes under some Borel equivalence relation and the interpretations of the relations and function symbols are uniformly Borel. We also investigate Borel isomorphisms between Borel structures.
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  7. Antonín Kučera & André Nies (2011). Demuth Randomness and Computational Complexity. Annals of Pure and Applied Logic 162 (7):504-513.
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  8. Bjørn Kjos-Hanssen, André Nies, Frank Stephan & Liang Yu (2010). Higher Kurtz Randomness. Annals of Pure and Applied Logic 161 (10):1280-1290.
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  9. Patricia Blanchette, Kit Fine, Heike Mildenberger, André Nies, Anand Pillay, Alexander Razborov, Alexandra Shlapentokh, John R. Steel & Boris Zilber (2009). Notre Dame, Indiana May 20–May 23, 2009. Bulletin of Symbolic Logic 15 (4).
    Direct download  
     
    My bibliography  
     
    Export citation  
  10. Bjørn Kjos-Hanssen & Andrée Nies (2009). Superhighness. Notre Dame Journal of Formal Logic 50 (4):445-452.
    We prove that superhigh sets can be jump traceable, answering a question of Cole and Simpson. On the other hand, we show that such sets cannot be weakly 2-random. We also study the class $superhigh^\diamond$ and show that it contains some, but not all, of the noncomputable K-trivial sets.
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  11. André Nies & Pavel Semukhin (2009). Finite Automata Presentable Abelian Groups. Annals of Pure and Applied Logic 161 (3):458-467.
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  12. Santiago Figueira, André Nies & Frank Stephan (2008). Lowness Properties and Approximations of the Jump. Annals of Pure and Applied Logic 152 (1):51-66.
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  13. André Nies (2007). Describing Groups. Bulletin of Symbolic Logic 13 (3):305-339.
    Two ways of describing a group are considered. 1. A group is finite-automaton presentable if its elements can be represented by strings over a finite alphabet, in such a way that the set of representing strings and the group operation can be recognized by finite automata. 2. An infinite f.g. group is quasi-finitely axiomatizable if there is a description consisting of a single first-order sentence, together with the information that the group is finitely generated. In the first part of the (...)
    Direct download (5 more)  
     
    My bibliography  
     
    Export citation  
  14. Rod Downey, Denis R. Hirschfeldt, André Nies & Sebastiaan A. Terwijn (2006). Calibrating Randomness. Bulletin of Symbolic Logic 12 (3):411-491.
    Direct download (10 more)  
     
    My bibliography  
     
    Export citation  
  15. Rod Downey, Andre Nies, Rebecca Weber & Liang Yu (2006). Lowness and Π₂⁰ Nullsets. Journal of Symbolic Logic 71 (3):1044-1052.
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  16. Wolfgang Merkle, Joseph S. Miller, André Nies, Jan Reimann & Frank Stephan (2006). Kolmogorov–Loveland Randomness and Stochasticity. Annals of Pure and Applied Logic 138 (1):183-210.
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  17. Joseph S. Miller & André Nies (2006). Randomness and Computability: Open Questions. Bulletin of Symbolic Logic 12 (3):390-410.
  18. Rod Downey, Denis R. Hirschfeldt, Joseph S. Miller & André Nies (2005). Relativizing Chaitin's Halting Probability. Journal of Mathematical Logic 5 (02):167-192.
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  19. Joos Heintz, Antonın Kucera, Joseph Miller, André Nies, Jan Reimann, Theodore Slaman, Diego Vaggione, Paul Vitányi & Verónica Becher (2005). Córdoba, Argentina September 20–24, 2004. Bulletin of Symbolic Logic 11 (4).
    Direct download  
     
    My bibliography  
     
    Export citation  
  20. André Nies, Frank Stephan & Sebastiaan A. Terwijn (2005). Randomness, Relativization and Turing Degrees. Journal of Symbolic Logic 70 (2):515 - 535.
    We compare various notions of algorithmic randomness. First we consider relativized randomness. A set is n-random if it is Martin-Löf random relative to θ(n−1). We show that a set is 2-random if and only if there is a constant c such that infinitely many initial segments x of the set are c-incompressible: C(x) ≥ |x| − c. The 'only if' direction was obtained independently by Joseph Miller. This characterization can be extended to the case of time-bounded C-complexity. Next we prove (...)
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  21. André Nies (2003). Parameter Definability in the Recursively Enumerable Degrees. Journal of Mathematical Logic 3 (01):37-65.
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  22. Douglas Cenzer & Andre Nies (2001). Initial Segments of the Lattice of Π01 Classes. Journal of Symbolic Logic 66 (4):1749 - 1765.
    We show that in the lattice E Π of Π 0 1 classes there are initial segments [ $\emptyset$ , P] = L(P) which are not Boolean algebras, but which have a decidable theory. In fact, we will construct for any finite distributive lattice L which satisfies the dual of the usual reduction property a Π 0 1 class P such that L is isomorphic to the lattice L(P)*, which is L(P), modulo finite differences. For the 2-element lattice, we obtain (...)
    Direct download (5 more)  
     
    My bibliography  
     
    Export citation  
  23. Steffen Lempp, André Nies & D. Reed Solomon (2001). On the Filter of Computably Enumerable Supersets of an R-Maximal Set. Archive for Mathematical Logic 40 (6):415-423.
    We study the filter ℒ*(A) of computably enumerable supersets (modulo finite sets) of an r-maximal set A and show that, for some such set A, the property of being cofinite in ℒ*(A) is still Σ0 3-complete. This implies that for this A, there is no uniformly computably enumerable “tower” of sets exhausting exactly the coinfinite sets in ℒ*(A).
    No categories
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  24. André Nies (2001). Interpreting in the Computably Enumerable Weak Truth Table Degrees. Annals of Pure and Applied Logic 107 (1-3):35-48.
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  25. André Nies & Andrea Sorbi (2000). Structural Properties and Σ02 Enumeration Degrees. Journal of Symbolic Logic 65 (1):285 - 292.
    We prove that each Σ 0 2 set which is hypersimple relative to $\emptyset$ ' is noncuppable in the structure of the Σ 0 2 enumeration degrees. This gives a connection between properties of Σ 0 2 sets under inclusion and and the Σ 0 2 enumeration degrees. We also prove that some low non-computably enumerable enumeration degree contains no set which is simple relative to $\emptyset$ '.
    Direct download (5 more)  
     
    My bibliography  
     
    Export citation  
  26. André Nies (1999). A New Spectrum of Recursive Models. Notre Dame Journal of Formal Logic 40 (3):307-314.
    We describe a strongly minimal theory S in an effective language such that, in the chain of countable models of S, only the second model has a computable presentation. Thus there is a spectrum of an -categorical theory which is neither upward nor downward closed. We also give an upper bound on the complexity of spectra.
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  27. Bakhadyr Khoussainov, Andre Nies & Richard A. Shore (1997). Computable Models of Theories with Few Models. Notre Dame Journal of Formal Logic 38 (2):165-178.
    In this paper we investigate computable models of -categorical theories and Ehrenfeucht theories. For instance, we give an example of an -categorical but not -categorical theory such that all the countable models of except its prime model have computable presentations. We also show that there exists an -categorical but not -categorical theory such that all the countable models of except the saturated model, have computable presentations.
    Direct download (6 more)  
     
    My bibliography  
     
    Export citation  
  28. André Nies, Richard A. Shore & Theodore A. Slaman (1996). Definability in the Recursively Enumerable Degrees. Bulletin of Symbolic Logic 2 (4):392-404.
    Direct download (7 more)  
     
    My bibliography  
     
    Export citation  
  29. Steffen Lempp & André Nies (1995). The Undecidability of the II4 Theory for the R. E. Wtt and Turing Degrees. Journal of Symbolic Logic 60 (4):1118 - 1136.
    We show that the Π 4 -theory of the partial order of recursively enumerable weak truth-table degrees is undecidable, and give a new proof of the similar fact for r.e. T-degrees. This is accomplished by introducing a new coding scheme which consists in defining the class of finite bipartite graphs with parameters.
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  30. Steffen Lempp & Andre Nies (1995). The Undecidability of the II$^_4$ Theory for the R. E. Wtt and Turing Degrees. Journal of Symbolic Logic 60 (4):1118-1136.
    We show that the $\Pi_4$-theory of the partial order of recursively enumerable weak truth-table degrees is undecidable, and give a new proof of the similar fact for r.e. T-degrees. This is accomplished by introducing a new coding scheme which consists in defining the class of finite bipartite graphs with parameters.
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  31. André Nies & Richard A. Shore (1995). Interpreting True Arithmetic in the Theory of the R.E. Truth Table Degrees. Annals of Pure and Applied Logic 75 (3):269-311.
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  32. André Nies (1994). Recursively Enumerable Equivalence Relations Modulo Finite Differences. Mathematical Logic Quarterly 40 (4):490-518.
    No categories
    Direct download (5 more)  
     
    My bibliography  
     
    Export citation  
  33. Klaus Ambos-Spies & André Nies (1992). Cappable Recursively Enumerable Degrees and Post's Program. Archive for Mathematical Logic 32 (1):51-56.
    We give a simple structural property which characterizes the r.e. sets whose (Turing) degrees are cappable. Since cappable degrees are incomplete, this may be viewed as a solution of Post's program, which asks for a simple structural property of nonrecursive r.e. sets which ensures incompleteness.
    No categories
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  34. Klaus Ambos-Spies, André Nies & Richard A. Shore (1992). The Theory of the Recursively Enumerable Weak Truth-Table Degrees is Undecidable. Journal of Symbolic Logic 57 (3):864-874.
    We show that the partial order of Σ0 3-sets under inclusion is elementarily definable with parameters in the semilattice of r.e. wtt-degrees. Using a result of E. Herrmann, we can deduce that this semilattice has an undecidable theory, thereby solving an open problem of P. Odifreddi.
    Direct download (6 more)  
     
    My bibliography  
     
    Export citation