Here are some recent publications of members of the Laboratory for Discrete Mathematics and Theoretical Computer Science:

2012
  • Margaret Archibald, Arnold Knopfmacher, and Toufik Mansour. Variation Statistics on Compositions. Fundamenta Informaticae, 117(1):1-17, 2012.

  • Peter Dankelmann, David Erwin, Wayne Goddard, Simon Mukwembi, and Henda C. Swart. Eccentric counts, connectivity and chordality. Information Processing Letters, 112(24):944-947, 2012.

  • Eric Allender and Holger Spakowski. Avoiding Simplicity is Complex. Theory of Computing Systems, 51(3):282-296, 2012.

  • Peter Dankelmann, David Erwin, Simon Mukwembi, Bernado Rodrigues, Eric Mwambene, and Gert Sabidussi. Automorphism group and diameter of a graph. Journal of Graph Theory, 70(1):80-91, 2012.
2011
2010
  • Margaret Archibald, Arnold Knopfmacher and Toufik Mansour. Compositions and samples of geometric random variables with constrained multiplicities. Discrete Mathematics and Theoretical Computer Science, proc. AN:449-460, 2010.

  • Vasco Brattka and Ruth Dillhage. Computability of finite-dimensional linear subspaces and best approximation. Annals of Pure and Applied Logic, 162:182-193, 2010.

  • Vasco Brattka and Arno Pauly. Computation with Advice. In Xizhong Zheng and Ning Zhong (eds.). Computability and Complexity in Analysis (CCA 2010). Electronic Proceedings in Theoretical Computer Science, 24:41-55, 2010.
2009
  • Margaret Archibald, Vasco Brattka, Valentin Goranko, and Benedikt Löwe, editors. Infinity in Logic and Computation, volume 5489 of Lecture Notes in Artificial Intelligence, Berlin, 2009. Springer. Selected Papers of the International Conference ILC 2007 held in Cape Town, South Africa, November 2007.

  • Margaret Archibald, and Arnold Knopfmacher. The average position of the dth maximum in a sample of geometric random variables. Statist. Probab. Lett., 79(7):864-872, 2009.

  • Margaret Archibald, and Conrado Martinez. The Hiring Problem and Permutations. Discrete Mathematics and Theoretical Computer Science, proc. AK:63-76, 2009.

  • Vasco Brattka. A computable version of Banach's inverse mapping theorem. Annals of Pure and Applied Logic, 157:85-96, 2009.

  • Vasco Brattka and Guido Gherardi. Borel complexity of topological operations on computable metric spaces. Journal of Logic and Computation, 19(1):45-76, 2009.

  • Vasco Brattka and Guido Gherardi. Effective Choice and Boundedness Principles in Computable Analysis. In A. Bauer, P. Hertling and Ker-I Ko (eds), Proceedings of the Sixth International Conference on Computability and Complexity in Analysis, 18-22 August 2009, Slovenia. Slovenia: Schloss Dagstuhl.

  • Vasco Brattka and Guido Gherardi. Weihrauch Degrees, Omniscience Principles and Weak Computability. In A. Bauer, P. Hertling and Ker-I Ko (eds), Proceedings of the Sixth International Conference on Computability and Complexity in Analysis, 18-22 August 2009, Slovenia. Slovenia: Schloss Dagstuhl.

  • Gábor Erdélyi, Lane A. Hemaspaandra, Jörg Rothe and Holger Spakowski. Generalized juntas and NP-hard sets. Theoretical Computer Science, 410(38-40):3995-4000, 2009.

  • Gábor Erdélyi, Lane A. Hemaspaandra, Jörg Rothe and Holger Spakowski. Frequency of correctness versus average polynomial time. Information Processing Letters, 109(16):946–949, 2009.

  • Holger Spakowski and Rahul Tripathi. Hierarchical unambiguity. SIAM Journal of Computing, 38(5):2079-2112, 2008/2009.
2008
  • Margaret Archibald, Vasco Brattka, and Clemens Heuberger. Randomness with respect to the signed-digit representation. Fundamenta Informaticae, 83(1-2):1-19, 2008.

  • Margaret Archibald and Conrado Martínez. The hiring problem in permutations (Spanish). Sixth Conference on Discrete Mathematics and Computer Science (Spanish), 77–84, Univ. Lleida, Lleida, 2008.

  • Vasco Brattka, Ruth Dillhage, Tanja Grubba, and Angela Klutsch, editors. Proceedings of the Fifth International Conference on Computability and Complexity in Analysis, volume 221 of Electronic Notes in Theoretical Computer Science, Amsterdam, 2008. Elsevier. CCA 2008, Hagen, Germany, August 21-24, 2008.

  • Vasco Brattka, Peter Hertling, and Klaus Weihrauch. A tutorial on computable analysis. In S. Barry Cooper, Benedikt Löwe, and Andrea Sorbi, editors, New Computational Paradigms: Changing Conceptions of What is Computable, pages 425-491. Springer, New York, 2008.

  • Vasco Brattka, Hajime Ishihara, Matthias Schröder, and Ning Zhong, editors. Computability and Complexity in Analysis, volume 14 of Journal of Universal Computer Science, Graz, 2008. Graz University of Technology. Selected Papers of the Fourth International Conference on Computability and Complexity in Analysis, June 16-18, 2007, Siena, Italy.

  • Vasco Brattka, Hajime Ishihara, Matthias Schröder, and Ning Zhong, editors. Computability and Complexity in Analysis, volume 54 of Mathematical Logic Quarterly, Weinheim, 2008. Wiley-VCH. Selected Papers of the Fourth International Conference on Computability and Complexity in Analysis, June 16-18, 2007, Siena, Italy.

  • Vasco Brattka, Gerhard Jäger, and Hans-Peter Künzi, editors. Logic and Information, From Logic to Constructive Reasoning, volume 76 of The Journal of Logic and Algebraic Programming, Amsterdam, 2008. Elsevier. Selected Papers of the Swiss-South-African joint seminar, University of Bern, Switzerland, January 22-25, 2007.

  • Vasco Brattka. Borel complexity and computability of the Hahn-Banach Theorem. Archive for Mathematical Logic, 46(7-8):547-564, 2008.

  • Vasco Brattka. Plottable real number functions and the computable graph theorem. SIAM Journal on Computing, 38(1):303-328, 2008.

  • Ruth Dillhage and Vasco Brattka. Computability of the metric projection onto finite-dimensional linear subspaces. In Vasco Brattka, Ruth Dillhage, Tanja Grubba, and Angela Klutsch, editors, CCA 2008, Fifth International Conference on Computability and Complexity in Analysis, volume 221 of Electronic Notes in Theoretical Computer Science, pages 45-60. Elsevier, 2008. CCA 2008, Fifth International Conference, Hagen, Germany, August 21-24, 2008.

  • Andrew N.W. Hone and Christine Swart. Integrality and the Laurent phenomenon for Somos 4 and Somos 5 sequences. Math. Proc. Cambridge Philos. Soc., 145(1):65-85, 2008.
2007
  • Margaret Archibald and Arnold Knopfmacher. The average position of the first maximum in a sample of geometric random variables. Discrete Mathematics and Theoretical Computer Science, AH:269-278, 2007. Special issue devoted to AofA07 (DMTCS Proceedings Series).

  • Margaret Archibald, Vasco Brattka, and Clemens Heuberger. Randomness with respect to the signed-digit representation. Report 2007-13, Institut für Optimierung und Diskrete Mathematik, TU Graz, Graz, September 2007.

  • Vasco Brattka and Ruth Dillhage. On computable compact operators on Banach spaces. In Douglas Cenzer, Ruth Dillhage, Tanja Grubba, and Klaus Weihrauch, editors, Proceedings of the Third International Conference on Computability and Complexity in Analysis, volume 167 of Electronic Notes in Theoretical Computer Science, pages 365-386, Amsterdam, 2007. Elsevier. CCA 2006, Gainesville, Florida, USA, November 1-5, 2006.

  • Vasco Brattka and Ruth Dillhage. On computable compact operators on computable Banach spaces with bases. Mathematical Logic Quarterly, 53(4-5):345-364, 2007.

  • Vasco Brattka and Guido Gherardi. Borel complexity of topological operations on computable metric spaces. In S. Barry Cooper, Benedikt Löwe, and Andrea Sorbi, editors, Computation and Logic in the Real World, volume 4497 of Lecture Notes in Computer Science, pages 83-97, Berlin, 2007. Springer. Third Conference on Computability in Europe, CiE 2007, Siena, Italy, June 18-23, 2007.

  • Vasco Brattka, Christiane Frougny, and Norbert Müller, editors. Real Numbers, volume 41 of Theoretical Informatics and Applications, Les Ulis, 2007. EDP Sciences. Selected Papers of the 6th conference on Real Numbers and Computers, Dagstuhl, Germany, November 15-17, 2004.

  • Vasco Brattka. From Hilbert's 13th Problem to the theory of neural networks: constructive aspects of Kolmogorov's Superposition Theorem. In Éric Charpentier, Annick Lesne, and Nikolai Nikolski, editors, Kolmogorov's Heritage in Mathematics, pages 253-280. Springer, Berlin, 2007.

  • G. Erdelyi, Lane A. Hemaspaandra, Jörg Rothe, and Holger Spakowski. On approximating optimal weighted lobbying, and frequency of correctness versus average-case polynomial time. In Fundamentals of Computation Theory 2007, pages 300-311, Berlin, August 2007. Springer.

  • Tobias Riege, Jörg Rothe, Holger Spakowski, and Masaki Yamamoto. An improved exact algorithm for the domatic number problem. Information Processing Letters, 101(3):101-106, 2007.

  • Holger Spakowski and Rahul Tripathi. Hierarchical unambiguity. Technical Report cs.CC/0702047, Computing Research Repository (CoRR), 2007.

  • Holger Spakowski and Rahul Tripathi. On the power of unambiguity in alternating machines. Theory of Computing Sytems, 41(2):291-326, 2007.
2006
  • Vasco Brattka and Ruth Dillhage. On computable compact operators on Banach spaces. In Douglas Cenzer, Ruth Dillhage, Tanja Grubba, and Klaus Weihrauch, editors, CCA 2006, Third International Conference on Computability and Complexity in Analysis, volume 333 of Informatik Berichte, pages 49-66. FernUniversität in Hagen, September 2006. CCA 2006, Gainesville, Florida, USA, November 1-5, 2006.

  • Vasco Brattka and Atsushi Yoshikawa. Towards computability of elliptic boundary value problems in variational formulation. Journal of Complexity, 22(6):858-880, 2006.

  • Vasco Brattka, Peter Hertling, Ker-I Ko, and Hideki Tsuiki, editors. Computability and Complexity in Analysis, volume 522 of Journal of Complexity, Amsterdam, 2006. Elsevier. Selected Papers of the International Conference CCA 2005, held in Kyoto, Japan, August 25-29, 2005.

  • Vasco Brattka. Computable versions of the uniform boundedness theorem. In Z. Chatzidakis, P. Koepke, and W. Pohlers, editors, Logic Colloquium 2002, volume 27 of Lecture Notes in Logic, pages 130-151, Urbana, 2006. Association for Symbolic Logic.

  • Christine S. Swart and Alf van der Poorten. Recurrence relations for elliptic sequences: Every Somos 4 is a Somos k. Bulletin of the London Mathematical Society, 38(4):546-554, 2006.
2005
  • Vasco Brattka and Ruth Dillhage. Computability of the spectrum of self-adjoint operators. Journal of Universal Computer Science, 11(12):1884-1900, 2005.

  • Vasco Brattka and Matthias Schröder. Computing with sequences, weak topologies and the axiom of choice. In Luke Ong, editor, Computer science logic, volume 3634 of Lecture Notes in Computer Science, pages 462-476. Springer, 2005.

  • Vasco Brattka, Ludwig Staiger, and Klaus Weihrauch, editors. Proceedings of the 6th Workshop on Computability and Complexity in Analysis, volume 120 of Electronic Notes in Theoretical Computer Science, Amsterdam, 2005. Elsevier. 6th International Workshop, CCA 2004, Wittenberg, Germany, August 16-20, 2004.

  • Vasco Brattka. Computability on non-separable Banach spaces and Landau's theorem. In Laura Crosilla and Peter Schuster, editors, From Sets and Types to Topology and Analysis: Towards Practicable Foundations for Constructive Mathematics, pages 316-333. Oxford University Press, 2005.

  • a=""> Brattka. Effective Borel measurability and reducibility of functions. Mathematical Logic Quarterly, 51(1):19-44, 2005.

  • Vasco Brattka. On the Borel complexity of Hahn-Banach extensions. In Vasco Brattka, Ludwig Staiger, and Klaus Weihrauch, editors, Proceedings of the 6th Workshop on Computability and Complexity in Analysis, volume 120 of Electronic Notes in Theoretical Computer Science, pages 3-16, Amsterdam, 2005. Elsevier. 6th International Workshop, CCA 2004, Wittenberg, Germany, August 16-20, 2004.

  • Wayne Goddard, Christine S. Swart, and Henda C. Swart. On the graphs with maximum distance or k--diameter. Mathematica Slovaca, 55:131-139, 2005.
2004
  • Vasco Brattka, Peter Hertling, Ker-I Ko, and Ning Zhong, editors. Special Issue Computability and Complexity in Analysis, volume 50 of Mathematical Logic Quarterly, Weinheim, 2004. Wiley-VCH. Selected Papers of the International Conference CCA 2003, held in Cincinnati, Ohio, August 28-30, 2003.

  • Vasco Brattka. Du 13-ième problème de Hilbert à la théorie des réseaux de neurones : aspects constructifs du théorème de superposition de Kolmogorov. In Éric Charpentier, Annick Lesne, and Nikolai Nikolski, editors, L'héritage de Kolmogorov en mathématiques, pages 241-268. Éditions Belin, Paris, 2004.

  • Peter Dankelmann, Wayne Goddard, and Christine S. Swart. The average eccentricity of a graph and its subgraphs. Utilitas Mathematica, 41:41-51, 2004.

  • Martin Ziegler and Vasco Brattka. Computability in linear algebra. Theoretical Computer Science, 326(1-3):187-211, 2004.

 

This list will regularly be updated.