Centre for Discrete Mathematics and Theoretical Computer Science

Research Reports

001	J. Gibbons	An Initial-Algebra Approach to Directed Acyclic Graphs	04/1995
002	J. Gibbons	Computing Downwards Accumulations on Trees Quickly	03/1995
003	J. Gibbons	Deriving Tidy Drawings of Trees	06/1995
004	P.R. Hafner	Large Cayley Graphs and Digraphs with Small Degree and Diameter	06/1995
005	J. Gibbons	The Third Homomorphism Theorem	07/1995
006	J. Gibbons and K. Wansbrough	Tracing Lazy Functional Languages	08/1995
007	C. Calude and S. Yu	Language-Theoretic Complexity of Disjunctive Sequences	09/1995
008	G.J. Chaitin, A. Arslanov and C. Calude	Program-Size Complexity Computes the Halting Problem	09/1995
009	C. Calude and J. Hromkovic	Complexity: A Language-Theoretic Point of View	10/1995
010	L.S. Dediu	Higman's Embedding Theorem. An Elementary Proof	10/1995
011	A. Arslanov	Difference Splittings of Recursively Enumerable Sets	01/1996
012	I. Antoniou, B. Pavlov and A. Yafyasov	Quantum Electronic Devices Based on Metal-Dielectric Transition in Low-Dimensional Quantum Structures	04/1996
013	C. Calude and C. Grozea	Kraft-Chaitin Inequality Revisited	04/1996
014	C. Calude	Algorithmic Information Theory: Open Problems	05/1996
015	C. Calude, E. Calude, K. Svozil and S. Yu	Physical versus Computational Complementarity I	06/1996
016	C.J. Colbourn and P.B. Gibbons	Uniform Orthogonal Group Divisible Designs with Block Size Three	08/1996
017	B. Khoussainov	Randomness, Computability, and Algebraic Specifications	08/1996
018	B. Khoussainov and R.A. Shore	Scott Families and Computably Categorical Structures	09/1996
019	M.J. Dinneen, K. Cattell and M.R. Fellows	Forbidden Minors to Graphs with Small Feedback Sets	10/1996
020	D.S. Bridges and R. Mines	Sequentially Continuous Linear Mappings in Constructive Analysis	10/1996
021	C. Calude and F.W. Meyerstein	Is the Universe Lawful?	11/1996
022	I. Tomescu	On a problem of L. Priese	11/1996
023	P. Cholak, S.S. Goncharov, B. Khoussainov and R.A. Shore	Computably Categorical Structures and Expansions by Constants	11/1996
024	B. Khoussainov, A. Nies and R.A. Shore	Computably Presentable Models of Theories with Few Models	12/1996
025	C. Calude, E. Calude and B. Khoussainov	Deterministic Automata: Simulation, Universality and Minimality	12/1996
026	M.J. Dinneen, J.A. Ventura, M.C. Wilson and G. Zakeri	Compound Constructions of Minimal Broadcast Networks	01/1997
027	H. Ishihara, B. Khoussainov and A. Nerode	Decidable Kripke Models of Intuitionistic Theories	01/1997
028	N. Brand and M. Morton	Uniform Generalized Steinhaus Graphs	02/1997
029	R.J. Coles, R.G. Downey and B. Khoussainov	On Initial Segments of Computable Linear Orders	03/1997
030	S. Legg	Solomonoff Induction	03/1997
031	B. Khoussainov and R.A. Shore	Computable Isomorphisms, Degree Spectra of Relations, and Scott Families	04/1997
032	C.S. Calude, P.H. Hertling and B. Khoussainov	Do the Zeros of the Riemann's Zeta-Function Form a Random Sequence?	04/1997
033	Y. Wang	Randomness, Stochasticity and Approximations	04/1997
034	A. Arslanov	On a Conjecture of M. Van Lambalgen	05/1997
035	B. Khoussainov, A. Yakhnis and V. Yakhnis	Clusters of Two Player Games and Restricted Determinacy Theorem	05/1997
036	C.S. Calude, P.H. Hertling and K. Svozil	Embedding Quantum Universes into Classical Ones	05/1997
037	D.S. Bridges, F. Richman and P. Schuster	Linear Independence and Choice	05/1997
038	F. Richman and D.S. Bridges	A Constructive Proof of Gleason's Theorem	05/1997
039	C.S. Calude	A Genius' Story: Two Books on Godel	06/1997
040	E. Calude and M. Lipponen	Deterministic Incomplete Automata: Simulation, Universality and Complementarity	06/1997
041	M. Conder	Explicit Definition of the Binary Reflected Gray Codes	06/1997
042	M. Conder	Small Trivalent Graphs of Large Girth	06/1997
043	G. Alford	An Explicit Construction of a Universal Extended H System	08/1997
044	U. Guenther, P.H. Hertling, R. Nicolescu and M.R. Titchener	Representing Variable-Length Codes in Fixed-Length T-Depletion Format in Encoders and Decoders	08/1997
045	B. Khoussainov, A. Yakhnis and V. Yakhnis	Games with Unknown Past	08/1997
046	B. Khoussainov and A.M. Slinko	Nonassociative Computable Rings and Their Isomorphisms	08/1997
047	R.G. Downey	On the Universal Splitting Property	08/1997
048	R.G. Downey and A. Nies	Undecidability Results for Low Complexity Degree Structures	08/1997
049	R.G. Downey, M.R. Fellows and K.W. Regan	Parameterized Circuit Complexity and the W Hierarchy	08/1997
050	K. Cattell, M.J. Dinneen, R.G. Downey, M.R. Fellows and M.A. Langston	On Computing Graph Minors Obstruction Sets	08/1997
051	R.G. Downey and C.G. Jockusch Jr	Effective Presentability of Boolean Algebras of Cantor-Bendixson Rank 1	08/1997
052	R.G. Downey, M.R. Fellows, A. Vardy and G. Whittle	The Parameterized Complexity of Some Fundamental Problems in Coding Theory	08/1997
053	C.S. Calude and M. Lipponen	Computational Complementarity and Sofic Shifts	08/1997
054	C.S. Calude, E. Calude and B. Khoussainov	Finite Nondeterministic Automata: Simulation and Minimality	09/1997
055	M.J. Dinneen	Practical Enumeration Methods for Graphs of Bounded Pathwidth and Treewidth	09/1997
056	D.S. Bridges and L.S. Dediu	Paradise Lost, or Paradise Regained?	09/1997
057	P.H. Hertling	The Real Number Structure is Effectively Categorical	09/1997
058	H.W. Guesgen	Imprecise Reasoning about Geographic Information	09/1997
059	C.S. Calude, P.H. Hertling, B. Khoussainov and Y. Wang	Recursively Enumerable Reals and Chaitin Omega Numbers	10/1997
060	E. Calude and M. Lipponen	Minimal Deterministic Incomplete Automata	10/1997
061	P.H. Hertling and Y. Wang	Invariance Properties of Random Sequences	10/1997
062	C.S. Calude and A. Nies	Chaitin Omega Numbers and Strong Reducibilities	10/1997
063	C.S. Calude, L. Priese and L. Staiger	Disjunctive Sequences: An Overview	10/1997
064	P.H. Hertling	Surjective Functions on Computably Growing Cantor Sets	10/1997
065	P.H. Hertling	Embedding Cellular Automata into Reversible Ones	10/1997
066	V.E. Cazanescu	Feedback for Relations	11/1997
067	P.H. Hertling	The Effective Riemann Mapping Theorem	11/1997
068	D.S. Bridges and S. Reeves	Constructive Mathematics, in Theory and Programming Practice	11/1997
069	D.S. Bridges, F. Richman and P. Schuster	Adjoints, Absolute Values and Polar Decompostions	11/1997
070	D.S. Bridges, C. Calude, B. Pavlov and D. Stefanescu	The Constructive Implicit Function Theorem and Applications in Mechanics	11/1997
071	C. Martin-Vide and G. Paun	Cooperating Distributed Splicing Systems	12/1997
072	G. Paun	DNA Computing Based on Splicing: Universality Results	12/1997
073	G. Paun	Two-Level Distributed H Systems	12/1997
074	C.S. Calude and P.H. Hertling	Computable Approximations of Reals: An Information-Theoretic Analysis	12/1997
075	P.H. Hertling (editor)	Unconventional Models of Computation'98: Posters	01/1998
076	C. Martin-Vide, G. Paun, G. Rosenberg and A. Salomaa	X-Families: An Approach to the Study of Families of Syntactically Similar Languages	01/1998
077	P.H. Hertling	A Lower Bound for Range Enclosure in Interval Arithmetic	01/1998
078	R. Laue	Halvings on Small Point Sets	01/1998
079	P.H. Hertling and K. Weihrauch	Randomness Spaces	01/1998
080	M.J. Dinneen, G. Pritchard and M.C. Wilson	Degree- and Time- Constrained Broadcast Networks	04/1998
081	A. Arslanov	On Hypersimple Sets and Chaitin Complexity	04/1998
082	M.J. Dinneen	Group-Theoretic Methods for Designing Networks	05/1998
083	C.S. Calude, E. Calude and C. Stefanescu	Computational Complementarity for Mealy Automata	05/1998
084	C.S. Calude and M.J. Dinneen	Breaking the Turing Barrier	05/1998
085	P.C. Denny	Search and Enumeration Techniques for Incidence Structures	05/1998
086	C.S. Calude, W. Merkle and Y. Wang	A Note on Pseudorandom Generators	05/1998
087	H. Ishihara, B. Khoussainov and A. Nerode	Computable Kripke Models and Intermediate Logics	07/1998
088	L. Staiger	The Hausdorff Measure of Regular Omega-Languages is Computable	08/1998
089	F.W. Meyerstein	Is Movement An Illusion? Zeno's Paradox From a Modern Viewpoint	09/1998
090	C.S. Calude, R.J. Coles, P.H. Hertling and B. Khoussainov	Degree-Theoretic Aspects of Computably Enumerable Reals	09/1998
091	M.J. Dinneen (editor)	Abstracts of the 2nd Japan - New Zealand Workshop on Logic in Computer Science	10/1998
092	C.S. Calude and E. Calude	Bisimulations and Behaviour of Nondeterministic Automata	02/1999
093	C.S. Calude	A Glimpse into Algorithmic Information Theory	02/1999
094	C.S. Calude and R.J. Coles	On a Theorem of Solovay	02/1999
095	C.S. Calude	A Characterization of C.E. Random Reals	03/1999
096	L. Staiger	The Kolmogorov Complexity of Liouville Numbers	03/1999
097	A.M. Kraegeloh	Unstable Dynamics on a Markov Background and Stability in Average	03/1999
098	G. Paun	Computing with Membranes: A Variant	03/1999
099	C.S. Calude, K. Salomaa and S. Yu	Metric Lexical Analysis	03/1999
100	C.S. Calude, P.H. Hertling, H. Juergensen and K. Weihrauch	Randomness on Full Shift Spaces	04/1999
101	G. Paun and G. Thierrin	Multiset Processing by means of Systems of Sequential Transducers	04/1999
102	G. Paun	P Systems with Active Membranes: Attacking NP Complete Problems	05/1999
103	B. Assanovich and U. Guenther	Variable-Length Codes for Sources with Equiprobable Symbols	05/1999
104	R.M. Solovay	A Version of Ω for which ZFC can not Predict a Single Bit	05/1999
105	M.J. Dinneen and B. Khoussainov	Update Games and Update Networks	06/1999
106	C.S. Calude, E. Calude and K. Svozil	Quantum Correlations Conundrum: An Automaton-Theoretic Approach	06/1999
107	C.S. Calude, M.J. Dinneen and K. Svozil	Counterfactual Effect, the Halting Problem, and the Busy Beaver Function	07/1999
108	C. Grozea	Free-Extendible Prefix-Free Sets and an Extension of the Kraft-Chaitin Theorem	07/1999
109	C.S. Calude, E. Calude, T. Chiou, M. Dumitrescu and R. Nicolescu	Testing Computational Complementarity for Mermin Automata	07/1999
110	D.S. Bridges, C.S. Calude and L.S. Dediu (editors)	Abstracts of Constructivity, Complexity, and Fuzziness (CCF '99)	07/1999
111	M.J. Dinneen and B. Khoussainov	Automata with Equational Constraints	08/1999
112	C.S. Calude, H. Juergensen and S. Legg	Solving Problems with Finite Test Sets	09/1999
113	C.S. Calude, E. Calude and K. Svozil	Computational Complementarity for Probabilistic Automata	09/1999
114	C.S. Calude	Chaitin &\Omega; Numbers, Solovay Machines, and Incompleteness	10/1999
115	G. Kapoulas	Computable $p$-adic Numbers	11/1999
116	C.S. Calude, H. Ishihara and T. Yamaguchi	Minimal Programs Are Almost Optimal	11/1999
117	C.S. Calude, G. Paun and M. Tataram	A Glimpse into Natural Computing	12/1999
118	M.J. Dinneen and L. Xiong	The Minor-Order Obstructions for The Graphs of Vertex Cover Six	01/2000
119	G. Paun	Computing with Membranes (P Systems): Twenty Six Research Topics	02/2000
120	G. Krenn, J. Summhammer and K. Svozil	Interferometric Information Gain Versus Interaction-Free Measurement	02/2000
121	H. Havlicek, G. Krenn, J. Summhammer and K. Svozil	On Coloring the Rational Quantum Sphere	02/2000
122	K. Svozil	Solution of Problem No. 10769	02/2000
123	J. Castellanos, G. Paun and A. Rodriguez-Paton	Computing with Membranes: P Systems with Worm-Objects	02/2000
124	S.S. Goncharov and B. Khoussainov	Open Problems in the Theory of Constructive Algebraic Systems	03/2000
125	B. Khoussainov	On Computable Theoretic Properties of Structures and Their Cartesian Products	03/2000
126	B. Khoussainov	Algebraic Constraints, Automata, and Regular Languages	03/2000
127	M.J. Dinneen and B. Khoussainov	Update Networks and Their Routing Strategies	03/2000
128	B. Khoussainov and S. Rubin	Finite Automata and Isomorphism Types	03/2000
129	B. Khoussainov and R.A. Shore	Solutions of the Goncharov-Millar and Degree Spectra Problems in The Theory of Computable Models	03/2000
130	C.S. Calude, M.J. Dinneen and K. Svozil	Reflections on Quantum Computing	03/2000
131	B. Khoussainov and R.A. Shore	Effective Model Theory: The Number of Models and Their Complexity	03/2000
132	C.S. Calude and B. Pavlov	The Poincare-Hardy Inequality on the Complement of a Cantor Set	05/2000
133	M.D. Kearse and P.B. Gibbons	Computational Methods and New Results for Chessboard Problems	05/2000
134	C.S. Calude and M.J. Dinneen (editors)	The 5th Anniversary Workshop on Discrete Mathematics and Theoretical Computer Science	05/2000
135	R.G. Downey and G.L. LaForte	Presentations of Computably Enumerable Reals	05/2000
136	K. Svozil	Quantum Interfaces	05/2000
137	K. Svozil	Science at the Crossroad Between Randomness and Determinism	05/2000
138	C. Areces and V. Becher	Analytic AGM Revision	06/2000
139		--skipped--	07/2000
140	C.S. Calude, M.J. Dinneen and G. Paun (editors)	Pre-Proceedings of the Workshop on Multiset Processing	08/2000
141	C.S. Calude	Real Numbers: From Computable to Random	08/2000
142	R. Pemantle and M.C. Wilson	Asymptotics of Multivariate Sequences II. Multiple Points of the Singular Variety	08/2000
143	C.S. Calude	Who Is Afraid of Randomness?	09/2000
144	R.G. Downey, D.R. Hirschfeldt and A. Nies	Randomness, Computability, and Density	09/2000
145	K. Svozil	Quantum Information: The New Frontier	09/2000
146	C.S. Calude, M.J. Dinneen and C.-K. Shu	Computing 80 Initial Bits of A Chaitin Omega Number	11/2000
147	I. Antoniou, C.S. Calude and M.J. Dinneen (editors)	Supplemental Papers for the 2nd Unconventional Models of Computation Conference	11/2000
148	R.G. Downey, D.R. Hirschfeldt and G.L. LaForte	Randomness and Reducibility	01/2001
149	U. Guenther	T-Complexity and T-Information Theory -- an Executive Summary	02/2001
150	C.S. Calude and M. Dumitrescu	Entropic Measures, Markov Information Sources and Complexity	02/2001
151	H.L. Bodlaender, M.J. Dinneen and B. Khoussainov	On Game-Theoretic Models of Networks	04/2001
152	C.S. Calude, M.J. Dinneen and S. Sburlan (editors)	Supplemental Abstracts for DMTCS01	04/2001
153	U. Guenther	Matching T-Codes to a Source	04/2001
154	S. Filipp and K. Svozil	Boole-Bell-type Inequalities in Mathematica	05/2001
155	N. Donath and K. Svozil	Finding a State in a Haystack	05/2001
156	C.S. Calude and B. Pavlov	Coins, Quantum Measurements, and Turing's Barrier: Preliminary Version	06/2001
157	S.Y.P. Lee and M.J. Dinneen	A Conference Submission Web Server	06/2001
158	C. Grozea	Relations Between the Low Subrecursion Classes	07/2001
159	D.S. Bridges and L.S. Vita	A Constructive Theory of Point-Set Nearness	08/2001
160	F.W. Meyerstein and A.P. Moller	LifeTime: A Unified Study of Life (A Preliminary Version)	09/2001
161	C.S. Calude and E. Calude	The Bridge Crossing Problem: Draft Form	09/2001
162	D.R. Hirschfeldt, B. Khoussainov, R.A. Shore and A.M. Slinko	Degree Spectra and Computable Dimensions in Algebraic Structures	10/2001
163	B. Khoussainov	Algebraic Constraints, Automata, and Regular Languages (Revised)	11/2001
164	R.G. Downey, D.R. Hirschfeldt and B. Khoussainov	Uniformity in Computable Structure Theory	11/2001
165	D.S. Bridges, C.S. Calude and F. Kroon (editors)	Workshop on Truths and Proofs	11/2001
166	C.S. Calude	Incompleteness, Complexity, Randomness and Beyond	11/2001
167	C.S. Calude, M.J. Dinneen and C.-K. Shu	Computing a Glimpse of Randomness	12/2001
168	M. Deza, M. Dutour and E. Panteleev	Small Cones of Oriented Semi-Metrics	12/2001
169	M. Dutour and M. Deza	The Hypermetric Cone on Seven Vertices	12/2001
170	C.S. Calude and B. Pavlov	Coins, Quantum Measurements, and Turing's Barrier	12/2001
171	J.J. Arulanandham, C.S. Calude and M.J. Dinneen	Bead--Sort: A Natural Sorting Algorithm	01/2002
172	H. Ishihara, B. Khoussainov and S. Rubin	On Isomorphism Invariants of Some Automatic Structures	01/2002
173	R.G. Downey	Some Computability-Theoretical Aspects of Reals and Randomness	01/2002
174	B. Khoussainov	Games Played on Finite Graphs and Temporal Logic	01/2002
175	L. Staiger	How Large is the Set of Disjunctive Sequences?	01/2002
176	S.S. Goncharov and B. Khoussainov	On Complexity of Computatable $\aleph_1$--Categorical Models	01/2002
177	I. Tomescu	On the Number of Occurrences of All Short Factors in Almost All Words	02/2002
178	H. Ishihara and B. Khoussainov	Complexity of Some Infinite Games Played on Finite Graphs	02/2002
179	K. Svozil	Logical Equivalence Between Generalized Urn Models and Finite Automata	02/2002
180	C.S. Calude, E. Calude and S. Marcus	Passages of Proof	02/2002
181	B. Khoussainov and T. Kowalski	Computable Isomorphism of Boolean Algebras with Operators	03/2002
182	G.J. Chaitin	Meta-Mathematics and the Foundations of Mathematics	05/2002
183	K. Svozil	What Could be More Practical than a Good Interpretation?	05/2002
184	K. Svozil	n-ary Quantum Information Defined by State Partitions	05/2002
185	B. Khoussainov and S. Rubin	Some Thoughts On Automatic Structures	05/2002
186	J.J. Arulanandham	Implementing Bead--Sort with P systems	05/2002
187	V. Becher and G.J. Chaitin	Another Example of Higher Order Randomness	05/2002
188	G.J. Chaitin	Paradoxes of Randomness	05/2002
189	B. Khoussainov	Finite State Strategies in One Player McNaughton Games	05/2002
190	S.S. Goncharov and B. Khoussainov	Complexity of Computable Models	05/2002
191	L. Staiger and H. Yamasaki	A Simple Example of an omega-language Topologically Inequivalent to a Regular One	07/2002
192	L. Staiger	The Entropy of Lukasiewicz Languages	08/2002
193	N. Zhou	The Broadcasting Problem For Bounded-Degree Directed Networks	09/2002
194	M. Ohya and I.V. Volovich	A New Quantum Algorithm for NP-complete Problems	09/2002
195	C.S. Calude, M.J. Dinneen and F. Peper (editors)	Supplemental Papers for the 3nd Unconventional Models of Computation Conference	10/2002
196	L. Staiger	Weighted Finite Automata and Metrics in Cantor Space	10/2002
197	C.S. Calude, S. Marcus and L. Staiger	A Topological Characterization of Random Sequences	10/2002
198	V.A. Adamyan, C.S. Calude and B. Pavlov	A Quantum Scattering Approach to Undecidable Problems: Preliminary Version	10/2002
199	J.J. Arulanandham, C.S. Calude and M.J. Dinneen	Solving SAT with Bilateral Computing	12/2002
200	G. Kapoulas	Infinitesimals Via the Cofinite Filter	12/2002
201	A. Nies	Lowness Properties of Reals and Randomness	12/2002
202	A. Nies	Reals which Compute Little	12/2002
203	J. Yang and U. Guenther	An Improved T-Decomposition Algorithm	12/2002
204	U. Guenther	An Entropy Measure for Finite Strings based on the Shannon Entropy of a Code Set	12/2002
205	J. Walsh and M.J. Dinneen	Checking for Substructures in Graphs of Bounded Pathwidth and Treewidth	12/2002
206	S.S. Goncharov and B. Khoussainov	Computationally Complete Computably Enumerable Algebras (Removed)	01/2003
207	B. Khoussainov and T. Kowalski	Games on Graphs: Automata, Structure, and Complexity	01/2003
208	B. Khoussainov, S. Rubin and F. Stephan	Automatic linear orders and trees (Revised)	11/2003
209	B. Khoussainov, S. Rubin and F. Stephan	Definability and Regularity in Automatic Presentations of Subsystems of Arithmetic	01/2003
210	L. Staiger	Constructive Dimension equals Kolmogorov Complexity	01/2003
211	M. Margenstern	The Tiling of the Hyperbolic 4D Space by the 120-Cell Is Combinatoric	02/2003
212	S.A. Terwijn	Complexity and Randomness	03/2003
213	C.S. Calude, L. Staiger and K. Svozil	Randomness Relative to Cantor Expansions	04/2003
214	K. Svozil	Eutatic Quantum Codes	04/2003
215	C.S. Calude, M.J. Dinneen and V. Vajnovszki (editors)	Supplemental Papers for DMTCS03	05/2003
216	K. Svozil	Computational Universes	05/2003
217	C.S. Calude, E. Calude and M.J. Dinneen	What is the Value of Taxicab(6)?	05/2003
218	C.S. Calude and L. Staiger	Generalisations of Disjunctive Sequences	06/2003
219	C.S. Calude	Dialogues on Quantum Computing	06/2003
220	J.J. Arulanandham, C.S. Calude and M.J. Dinneen	A Fast Natural Algorithm for Searching	06/2003
221	E. Calude, B. Mills and L. Mills	A Uniform Method for Testing Computational Complementarity	06/2003
222	V. Becher, S. Figueira, A. Nies and S. Picchi	Program Size Complexity for Possibly Infinite Computations	08/2003
223	J.J. Arulanandham, C.S. Calude and M.J. Dinneen	Balance Machines: Computing = Balancing	10/2003
224	A. Moreira	RNA Rings in the Origin of Life	10/2003
225	S. Daniels	Uniform Candy Distribution	10/2003
226	C.S. Calude and G. Paun	Bio-Steps Beyond Turing	11/2003
227	H. Ishihara and L.S. Vita	A constructive Banach's inverse mapping theorem in F-spaces	12/2003
228	M.C. Wilson	Probability Generating Functions for Sattolo's Algorithm	01/2004
229	H. Ishihara	Informal Constructive Mathematics	01/2004
230	S. Filipp and K. Svozil	Testing the Bounds on Quantum Probabilities	01/2004
231	K. Svozil	Farewell to Quantum Contextuality?	01/2004
232	K. Svozil	Single Particle Interferometric Analogues of Multipartite Entanglement	01/2004
233	K. Svozil	Quantum Information via State Partitions and the Context Transition Principle	01/2004
234	A. Nies, F. Stephan and S.A. Terwijn	Randomness, Relativization, and Turing Degrees	02/2004
235	C.S. Calude and M.A. Stay	From Heisenberg to Goedel via Chaitin	02/2004
236	C.S. Calude and S. Marcus	Mathematical Proofs at a Crossroad?	03/2004
237	H. Juergensen, L. Staiger and H. Yamasaki	Finite Automata Encoding Geometric Figures	04/2004
238	S. Filipp and K. Svozil	The min-max Principle Generalizes Tsirelson's Bound	04/2004
239	C.S. Calude, L. Staiger and S.A. Terwijn	On Partial Randomness	04/2004
240	C.S. Calude, C. Campeanu and M. Dumitrescu	Automata Recognizing No Words: A Statistical Approach	05/2004
241	C.S. Calude and H. Juergensen	Is Complexity a Source of Incompleteness?	06/2004
242	A. Juarna and V. Vajnovszki	Fast Generation of Fibonacci Permutations	07/2004
243	M.A. Stay	Inexpensive Linear-Optical Implementations of Deutsch's Algorithm	07/2004
244	D. Schultes	Rainbow Sort:Sorting at the Speed of Light	07/2004
245	M. Harmer	Fitting Parameters for a Solvable Model of a Quantum Network	07/2004
246	C.S. Calude and G. Paun	Computing with Cells and Atoms: After Five Years	08/2004
247	C. Grozea	Plagiarism Detection with State of the Art Compression Programs	08/2004
248	C.S. Calude	Algorithmic Randomness, Quantum Physics, and Incompleteness	08/2004
249	M.A. Stay	Generalized Number Derivatives	08/2004
250	T. Forster	An Introduction to WQO and BQO Theory (Preliminary Version)	09/2004
251	C.S. Calude and S. Rudeanu	Proving as a Computable Procedure	10/2004
252	C.S. Calude, E. Calude, M.J. Dinneen (editors)	Supplemental Papers for DLT04	11/2004
253	M. Margenstern (editor)	Proceedings of the International Workshop on Tilings and Cellular Automata	11/2004
254	M.J. Dinneen and R. Lai	Properties of Vertex Cover Obstructions	11/2004
255	M.R. Titchener, T.A. Gulliver, R. Nicolescu, U. Speidel and L. Staiger	Deterministic Complexity and Entropy	12/2004
256	J.J. Arulanandham and M.J. Dinneen	Balance Machines: A New Formalism for Computing	12/2004
257	B. Khoussainov (editor)	Abstracts of the Workshop on Automata, Structures and Logic	12/2004
258	K. Svozil	Communication Cost of Breaking the Bell Barrier	12/2004
259	J. Yang and U. Speidel	A T-decomposition Algorithm with O(n log n) Time and Space Complexity	01/2005
260	H. Ishihara, R. Mines, P. Schuster, and L.S. Vita	Quasi-Apartness and Neighbourhood Spaces	03/2005
261	C.S. Calude, E. Calude and M.J. Dinneen	What is the Value of Taxicab(6)? An Update	04/2005
262	M.C. Wilson	Asymptotics for Generalized Riordan Arrays	04/2005
263	R. Pemantle and M.C. Wilson	Twenty Combinatorial Examples of Asymptotics Derived From Multivariate Generating Functions	04/2005
264	L. Staiger	Infinite Iterated Function Systems in Cantor Space and the Hausdorff Measure of omega-power Languages	04/2005
265	M.A. Stay	Very Simple Chaitin Machines for Concrete AIT	05/2005
266	R. Eimann, U. Speidel, N. Brownlee and J. Yang	Network Event Detection with T-Entropy	05/2005
267	M.R. Titchener, U. Speidel and J. Yang	A Comparison of Practical Information Measures	05/2005
268	D.M. Greenberger and K. Svozil	Quantum Theory Looks at Time Travel	06/2005
269	K. Svozil	Characterization of Quantum Computable Decision Problems by State Discrimination	06/2005
270	S. Comorosan	Computing with Molecules: A New Type of Quantum Molecular Computation	07/2005
271	M.A. Stay	Truth and Light: Physical Algorithmic Randomness	08/2005
272	L. Staiger	Hausdorff Measure and Lukasiewicz Languages	11/2005
273	C.S. Calude and M.A. Stay	Natural Halting Probabilities, Partial Randomness, and Zeta Functions	11/2005
274	G. Pritchard and M.C. Wilson	Exact Results on Manipulability of Positional Voting Rules	12/2005
275	N.J. Hay	Optimal Agents	12/2005
276	A. Juarna and V. Vajnovszki	Combinatorial Isomorphisms Beyond a Simion-Schmidt's Bijection	01/2006
277	C.S. Calude, E. Calude and M.J. Dinneen	A New Measure of the Difficulty of Problems	02/2006
278	S. Schwarz	Lukasiewicz Logics and Weighted Logics over MV-Semirings	05/2006
279	L. Staiger	The Kolmogorov Complexity of Infinite Words	05/2006
280	L. Staiger	On Maximal Prefix Codes	05/2006
281	G.J. Chaitin	Is Incompleteness A Serious Problem	07/2006
282	G.J. Chaitin	Speculations on Biology, Information and Complexity	07/2006
283	C.S. Calude and G.J. Chaitin	A Dialogue on Mathematics and Physics	07/2006
284	C.S. Calude and M.A. Stay	Most Short Programs Halt Quickly or Never Halt	08/2006
285	C.S. Calude	De-Quantising the Solution of Deutsch's Prolem	08/2006
286	U. Speidel	T-Complexity and T-Information Theory--an Executive Summary, 2nd revised version	10/2006
287	G. Pritchard and M.C. Wilson	Probability Calculations Under the IAC Hypothesis	10/2006
288	M.E. Lladser, P. Potocnik, J. Siran, J. Siagiova and M.C. Wilson	The Diameter of Random Cayley Digraphs of Given Degree	10/2006
289	G. Firror, T. Mansour and M.C. Wilson	Longest Alternating Subsequences in Pattern-Restricted Permutations	10/2006
290	T.A. Gulliver and U. Speidel	On T-Codes and Necklaces	10/2006
291	C.S. Calude and K. Svozil	Quantum Randomness and Value Indefiniteness	11/2006
292	C.S. Calude	Information: The Algorithmic Paradigm	12/2006
293	C.S. Calude and M.J. Dinneen	Exact Approximations of Omega Numbers	12/2006
294	G.J. Chaitin	How Much Information Can There Be in a Real Number	01/2007
295	M.C. Wilson	Random and Exhaustive Generation of Permuations and Cycles	01/2007
296	A. Raichev and M.C. Wilson	A New Method for Computing Asymptotics of Diagonal Coefficients of Multivariate Generating Functions	01/2007
297	N.J. Hay, A. Shorin and J. Wang (editors)	University of Auckland Computer Science Graduate Workshop 20‍06	01/2007
298	L. Staiger	Prefix-free Lukasiewicz Languages	01/2007
299	K. Svozil	Physical Unknowables	01/2007
300	N.J. Hay	Universal Semimeasures: An Introduction	02/2007
301	G. Pritchard and M.C. Wilson	Asymptotics of the Minimum Manipulating Coalition Size for Positional Voting Rules under IC Behaviour	02/2007
302	C.T. Chong, A. Nies and L. Yu	Higher Randomness Notions and Their Lowness Properties	03/2007
303	A. Nies	Describing Groups	03/2007
304	R.W. Doran	The Gray Code	03/2007
305	G.J. Chaitin	An Algebraic Characterization of the Halting Probability	04/2007
306	C.S. Calude and J. Gruska	Quantum Informatics and the Relations Between Informatics, Physics and Mathematics: A Dialogue	05/2007
307	A. Raichev and M.C. Wilson	Asymptotics of Diagonal Coefficients of Multivariate Generating Functions	05/2007
308	M. Zimand	Two Sources Are Better than One for Increasing the Kolmogorov Complexity of Infinite Sequences	05/2007
309	C.S. Calude, E. Calude and S. Marcus	Proving and Programming	06/2007
310	S. Drape	The Suitability of Different Binary Tree Obfuscations	06/2007
311	S. Drape and A. Majumdar	Design and Evaluation of Slicing Obfuscation	06/2007
312	C.S. Calude and L. Staiger	On Universal Computably Enumerable Prefix Codes	10/2007
313	Y.-B. Kim and M.J. Dinneen	A Repository of Compound Graphs for use in Large Network Design	11/2007
314	E. Goles, C. Littleand and I. Rapaport	The Underlying Optimal Protocol of Rule 218 Cellular Automaton	11/2007
315	A. Leitsch, G. Schachner and K. Svozil	How to Acknowledge Hypercomputation?	12/2007
316	B. Whitworth	The Physical World as a Virtual Reality	12/2007
317	C.S. Calude and M. Zimand	Algorithmically Independent Sequences	01/2008
318	A.A. Abbott and M.J. Dinneen	An Investigation of Algorithms to Aesthetically Draw Cayley Graphs	03/2008
319	K. Svozil	Aesthetic Complexity	04/2008
320	C.S. Calude and B.E. Carpenter	A Dialogue on the Internet	04/2008
321	J. Teutenberg (editor)	Proceedings of the Computer Graduate Workshop 2007	04/2008
322	A. Raichev and M.C. Wilson	A New Approach to Asymptotics of Maclaurin Coefficients of Algebraic Functions	04/2008
323	A. Raichev and M.C. Wilson	Asymptotics of Coefficients of Multivariate Generating Functions: Improvements for Smooth Points	05/2008
324	C.S. Calude	Incompleteness: A Personal Perspective	06/2008
325	G.J. Chaitin	The Halting Probability via Wang Tiles	06/2008
326	C.S. Calude, A. Nies, L. Staiger and F. Stephan	Universal Recursively Enumerable Sets of Strings	06/2008
327	C.S. Calude and J.F. Costa (editors)	Pre-proceedings of the Workshop Physics and Computation	07/2008
328	C.S. Calude and N.J. Hay	Every Computably Enumerable Random Real Is Provably Computably Enumerable Random	07/2008
329	M.J. Dinneen and A.J.L. Fenton	A New Linear-Time Dominating Number Algorithm for Graphs of Bounded Pathwidth	07/2008
330	B Kjos-Hanssen, A. Nies, F. Stephan and L. Yu	Higher Kurtz Randomness	08/2008
331	S. Figueira, J. Miller and A. Nies	Indifferent Sets	08/2008
332	M. Hoyrup	Computability, Randomness and Ergodic Theory on Metric Spaces	09/2008
333	C.R. Gonzalez	Randomness and Ergodic Theory: An Algorithmic Point of View	09/2008
334	L. Staiger	On Oscillation-free ε-random Sequences	09/2008
335	J. Mielke	Refined Bounds on Kolmorgorov Complexity for ω-Languages	09/2008
336	M.J. Dinneen and M. Khosravani	Searching for Spanning k-Caterpillars and k-Trees	09/2008
337	G.J. Chaitin	Evolution of Mutating Software	10/2008
338	C.S. Calude, H. Juergensen and L. Staiger	Topology on Words	11/2008
339	C.S. Calude	Simplicity via Provability for Universal Prefix-free Turing Machines	11/2008
340	C. Muller and M. Kohlhase	Communities of Practice in Mathematical E-Learning	11/2008
341	C. Muller and M. Kohlhase	Context-Aware Adaptation. A Case Study on Mathematical Notations	11/2008
342	R. Nicolescu, M.J. Dinneen and Y.-B. Kim	Structured Modelling with Hyperdag P Systems: Part A	12/2008
343	C.S. Calude and E. Calude	Evaluating the Complexity of Mathematical Problems. Part 1	12/2008
344	C.S. Calude and J.P. Lewis	Is there a Universal Image Generator	01/2009
345	M. Schimpf and K. Svozil	A Glance at Singlet States and Four-Partite Correlations	02/2009
346	K. Svozil	Some Observations Concerning the Plasticity of Nonlocal Quantum Correlations Exceeding Classical Expectations	02/2009
347	M. Schaller and K. Svozil	Scale-Invariant Cellular Automata and Recursive Petri Nets	02/2009
348	K. Svozil	Proposed Direct Test of Quantum Contextuality	02/2009
349	K. Svozil	Quantum Scholasticism: On Quantum Contexts, Counterfactuals, and the Absurdities of Quantum Omniscience	02/2009
350	C.S. Calude and L. Staiger	A Note on Accelerated Turing Machines	02/2009
351	P.H. Potgieter and E.E. Rosinger	Output Concepts for Accelerated Turing Machines	02/2009
352	J.C. Baez and M.A. Stay	Physics, Topology, Logic and Computation: A Rosetta Stone	03/2009
353	K. Svozil	Bertlmann's Chocolate Balls and Quantum Type Cryptography	03/2009
354	C.S. Calude and C. Müller	Formal Proof: Reconciling Correctness and Understanding	03/2009
355	K. Tadaki	Fixed Point Theorems on Partitial Randomness	03/2009
356	M.J. Dinneen, N.R. Ke and M. Khosravani	Arithmetic Progression Graphs	03/2009
357	R. Reyhani, G. Pritchard and M.C. Wilson	New Measures of the Diffculty of Manipulation of Voting Rules	03/2009
358	K. Tadaki	A Statistical Mechanical Interpretation of Algorithmic Information Theory III: Composite Systems and Fixed Points	04/2009
359	K. Tadaki	Chaitin Omega Numbers and Halting Problems	04/2009
360	K. Svozil	On the Brightness of the Thomson Lamp. A Prolegomenon to Quantum Recursion Theory	04/2009
361	K. Svozil	The Diagonalization Method in Quantum Recursion Theory	04/2009
362	K. Svozil	Three Criteria for Quantum Random Number Generators Based on Beam Splitters	04/2009
363	A. Nies	Lowness for Computable and Partial Computable Randomness	04/2009
364	K. Svozil	Randomness in Physics: Five Questions, Some Answers	05/2009
365	C.S. Calude, N.J. Hay and F. Stephan	Representation of Left-Computable ε-Random Reals	05/2009
366	J. Mielke and L. Staiger	On Oscillation-free ε-random Sequences II	07/2009
367	J. Hertel	On the Difficulty of Golbach and Dyson Conjectures	07/2009
368	C.S. Calude and E. Calude	The Complexity of the Four Colour Theorem	08/2009
369	C.S. Calude and E. Calude	Evaluating the Complexity of Mathematical Problems. Part 2	08/2009
370	E. Calude	The Complexity of Goldbach's Conjecture and Riemann's Hypothesis	08/2009
371	A.A. Abbott	The Deutsch-Jozsa Problem: De-quantization and Entanglement	08/2009
372	C.S. Calude, M.J. Dinneen, M. Dumitrescu and K. Svozil	How Random Is Quantum Randomness? (Extended Version)	12/2009
373	R. Nicolescu, M.J. Dinneen and Y.-B. Kim	Structured Modelling with Hyperdag P Systems: Part B	10/2009
374	C.S. Calude, K. Salomaa, and T.K. Roblot	Finite-State Complexity and Randomness	12/2009
375	M.J. Dinneen, Y.-B. Kim and R. Nicolescu	P Systems and the Byzantine Agreement	01/2010
376	M. Andreev, I. Razenshteyn and A. Shen	Not Every Domain of a Plain Decompressor Contains the Domain of a Prefix-Free One	02/2010
377	Y.I. Manin	Renormalization and Computation II: Time Cut-Off and the Halting Problem	02/2010
378	M.J. Dinneen, Y.-B. Kim and R. Nicolescu	Synchronization in P Modules	02/2010
379	V. Putz and K. Svozil	Can a Computer be “pushed” to Perform Faster-Than-Light?	03/2010
380	K. Tadaki	A New Representation of Chaitin Omega Number Based on Compressible Strings	04/2010
381	A.A. Abbott and C.S. Calude	Understanding the Quantum Computational Speed-up via De-quantisation	04/2010
382	C.S. Calude, M. Cavaliere and R. Mardare	An Observer-Based De-Quantisation of Deutsch's Algorithm	05/2010
383	E. Calude	Fermat's Last Theorem and Chaoticity	06/2010
384	C.S. Calude, E. Calude and K. Svozil	The Complexity of Proving Chaoticity and the Church-Turing Thesis	06/2010
385	S. Schwarz and L. Staiger	Topologies refining the CANTOR topology on X^Ω	06/2010
386	R. Polley and L. Staiger	The Maximal Subword Complexity of Quasiperiodic Infinite Words	06/2010
387	A.A. Abbott	De-quantisation of the Quantum Fourier Transform	06/2010
388	M.J. Dinneen, Y.-B. Kim and R. Nicolescu	A Faster P Solution for the Byzantine Agreement Problem	07/2010
389	K. Tadaki	Properties of Optimal Prefix-Free Machines as Instantaneous Codes	07/2010
390	B. Whitworth	The Light of Existence	08/2010
391	G.J. Chaitin	To a Mathematical Theory of Evolution and Biological Creativity	09/2010
392	A.A. Abbott and C.S. Calude	Von Neumann Normalisation of a Quantum Random Number Generator	10/2010
393	C.S. Calude, M.J. Dinneen and A.M. Gardner	Opening the Book of Randomness (Extended Version)	10/2010
394	M.J. Dinneen and M. Khosravani	Hardness of Approximation and Integer Programming Frameworks for Searching for Caterpillar Trees	11/2010
395	M.J. Dinneen, Y.-B. Kim and R. Nicolescu	Faster Synchronization in P Systems	11/2010
396	A.A. Abbott, C.S. Calude and K. Svozil	A Quantum Random Number Generator Certified by Value Indefiniteness	12/2010
397	G.J. Chaitin	A Mathematical Theory of Evolution and Biological Creativity	01/2011
398	Y. Bugeaud	Continued Fractions of Transcendental Numbers	02/2011
399	R. Nicolescu and H. Wu	BFS Solution for Disjoint Paths in P Systems	03/2011
400	A. Akhtarzada, C.S. Calude and J. Hosking	A Multi-Criteria Metric Algorithm for Recommender Systems	04/2011
401	G. Gimel'farb, R. Nicolescu and S. Ragavan	P Systems in Stereo Matching (extended version)	04/2011
402	L. Staiger	Constructive Dimension and Hausdorff Dimension: The Case of Exact Dimension	04/2011
403	U. Speidel	A Forward-Parsing Randomness Test Based on the Expected Codeword Length of T-codes	05/2011
404	M.J. Dinneen, Y.-B. Kim and R. Nicolescu	An Adaptive Algorithm for P System Synchronization	05/2011
405	A.A. Abbott, M. Bechmann, C.S. Calude, and A. Sebald	A Nuclear Magnetic Resonance Implementation of a Classical Deutsch-Jozsa Algorithm	05/2011
406	K. Tadaki	A Computational Complexity-Theoretic Elaboration of Weak Truth-Table Reducibility	07/2011
407	K. Svozil	Neutrino Dispersion Relation Changes Due to Radiative Corrections as the Origin of Faster-than-Light-in-Vacuum Propagation in a Medium	09/2011
408	A.A. Abbott, C.S. Calude and K. Svozil	On Demons and Oracles	11/2011
409	C.S. Calude, E. Calude and M.S. Queen	The Complexity of Euler's Integer Partition Theorem	11/2011
410	C.S. Calude and E. Calude	The Complexity of Mathematical Problems: An Overview of Results and Open Problems	11/2011
411	L. Staiger	On Oscillation-free Chaitin h-random Sequences	11/2011
412	L. Staiger	Asymptotic Subword Complexity	11/2011
413	D.H. Bailey, J.M. Borwein, C.S. Calude, M.J. Dinneen, M. Dumitrescu and A. Yee	An Empirical Approach to the Normality of π	11/2011
414	S. Datt and M.J. Dinneen	Towards Practical P Systems: Discovery Algorithms	12/2011
415	R. Nicolescu	Parallel and Distributed Algorithms in P Systems	12/2011
416	M. Burgin, C.S. Calude and E. Calude	Inductive Complexity Measures for Mathematical Problems	12/2011
417	R. Nicolescu and H. Wu	New Solutions for Disjoint Paths in P Systems	03/2012
418	J. Hertel	Inductive Complexity of Goodstein's Theorem	04/2012
419	L. Staiger	A Correspondence Principle for Exact Constructive Dimension	04/2012
420	M. McKubre-Jordens and R. Sainudiin (eds.)	Construmath South 2012	04/2012
421	A. Raichev	Leinartas's Partial Fraction Decomposition	06/2012
422	A.A. Abbott, C.S. Calude, J. Conder and K. Svozil	Kochen-Specker Theorem Revisited and Strong Incomputability of Quantum Randomness	07/2012
423	M.J. Dinneen and Y.-B. Kim	A New Universality Result on P Systems	07/2012
424	M.J. Dinneen and K. Wei	On the Analysis of a (1+1) Self-Adjusting Memetic Algorithm	08/2012
425	S. Hartmann and S. Link	The Implication Problem of Data Dependencies over SQL Table Definitions: Axiomatic, Algorithmic and Logical Characterizations	10/2012
426	M. Kirchberg, S. Hartmann and S. Link	Design by Example for SQL Table Definitions with Functional Dependencies	10/2012
427	F. Ferrarotti, S. Hartmann and S. Link	Efficiency Frontiers of XML Cardinality Constraints	10/2012
428	S. Link	Sound Approximate Reasoning about Saturated Conditional Probabilistic Independence under Controlled Uncertainty	10/2012
429	C.S. Calude, E. Calude and M.S. Queen	Inductive Complexity of the P Versus NP Problem	10/2012
430	M.J. Dinneen and R. Versteegen	Obstructions for the Graphs of Vertex Cover Seven	12/2012
431	H. ElGindy, R. Nicolescu and H. Wu	Fast Distributed DFS Solutions for Edge-disjoint Paths in Digraphs	03/2012
432	Y. I. Manin	Zipf's Law and L. Levin's Probability Distributions	02/2013
433	G. Altmann, I.-I. Popescu and D. Zotta	Stratification in Texts	02/2013
434	C.S. Calude and K. Tadaki	Spectral Representation of Some Computably Enumerable Sets With an Application to Quantum Provability	03/2013
435	K. Tadaki and N. Doi	Cryptography and Algorithmic Randomness	04/2013
436	K. Tadaki	Phase Transition and Strong Predictability	04/2013
437	A. Probert and M.J. Dinneen	Branchwidth, Branch Decompositions and b-parses	04/2013
438	Y. I. Manin	My Life Is not a Conveyor Belt	05/2013