1,568 research outputs found
Bisimulations and Behaviour of Nondeterministic Automata
No full textThe minimization of nondeterministic automata without initial states (developed
within a game-theoretic framework in Calude, Calude, Khoussainov [3]) is presented
in terms of bisimulations; the minimal automaton is unique up to an isomorphism
in case of reversible automata. We also prove that there exists an in nite class
of (strongly connected) nondeterministic automata each of which is not bisimilar
with any deterministic automaton. This shows that in the sense of bisimilarity
nondeterministic automata are more powerful than deterministic ones. It is an open
question whether the method of bisimulations can produced, in general, the unique
minimal nondeterministic automaton
Supplemental Papers for the 3nd Unconventional Models of Computation Conference
No full textThese are additional abstracts of talks that were presented at the Third International Conference on Unconventional Models of Computation (UMC’02). Computer Science, and the Kansai Advanced Research Centre of the Communications Research Laboratory was held at the Orbis hall in the centre of Kobe’s Rokko island, during October 15-19, 2002. The conference encompasses all areas of unconventional computation, especially quantum computing, DNA-based computation, evolutionary algorithms and other proposals for computation models that go beyond the Turing model. Additional refereed and invited papers of UMC’02 appear in the following proceedings: C.S. Calude, M.J. Dinneen, and F. Peper editors. Unconventional Models of Computation, UMC’02, LNCS 2509, Springer-Verlag, October 2002, VIII+300 pages
The 5th Anniversary Workshop on Discrete Mathematics and Theoretical Computer Science
No full textThese are the abstracts of talks to be given at the One-Day Workshop Discrete Mathematics and
Theoretical Computer Science Day to be held at the University Auckland on 26 May 2000 to mark the
5th anniversary of the Center for Discrete Mathematics and Theoretical Computer Science.
The Conference Committee for the workshop consisted of the following people: Douglas S. Bridges,
Canterbury, Cristian S. Calude, Auckland, Michael J. Dinneen, Auckland, John Hosking, Auckland,
Gaven Martin, Auckland, Alan Williamson, Auckland
Minimal Deterministic Incomplete Automata
No full textWe construct a minimal automaton for an output-incomplete Moore automaton. The approach is motivated by physical interpretation of seeing deterministic finite automata as models for elementary particles. When compared to some classical methods our minimal automaton is unique up to an isomorphism and preserves also the undefined or unspecified behaviour of the original automaton. 1.) Proceedings of the First Japan--New Zealand Workshop on Logic in Computer Science, special issue editors D.S. Bridges, C.S. Calude, M.J. Dinneen and B. Khoussainov. 2.)On leave from the Department of Mathematics, University of Turku, Finland
Chaitin Ω Numbers and Strong Reducibilities
No full textWe prove that any Chaitin Ω number (i.e., the halting probability of a universal self-delimiting Turing machine) is wtt-complete, but not tt-complete. In this way we obtain a whole class of natural examples of wtt-complete but not tt-complete r.e. sets. The proof is direct and elementary. 1.) Proceedings of the First Japan-New Zealand Workshop on Logic in Computer Science, special issue editors D.S. Bridges, C.S. Calude, M.J. Dinneen and B. Khoussainov. 2.) Partially supported by AURC A18/XXXXX/62090/F3414056, 1997. 3.) Partially supported by NSF Grant DMS-9500983
On the maximum coefficients of rational formal series in commuting variables
No full textWe study the maximum function of any R+-rational formal series S in two commuting variables, which assigns to every integer n is an element of N, the maximum coefficient of the monomials of degree n. We show that if S is a power of any primitive rational formal series, then its maximum function is of the order Theta(n(k/2)gimel(n)) for some integer k greater than or equal to -1 and some positive real lambda. Our analysis is related to the study of limit distributions in pattern statistics. In particular, we prove a general criterion for establishing Gaussian local limit laws for sequences of discrete positive random variables
Optimum Extendible Prefix Codes
No full textSuppose that we have L messages coded by a prefix code (over an alphab et M with m letters) having a minimum weighted length. The problem addressed in this paper is the following: How to find s codewords for new messages so that by leaving unchanged the codification of the first L messages (by compatibility rea sons), the resulting extended code is still prefix (over M) and has a minimum weighted length? To this aim we introduce the notion of optimum extendible prefix code and then, by modifying Huffman s algorithm, we give an effcient algorithm to construct the opti mum extension of a non-complete prefix code, provided the initial code is optimal. 1.) Proceedings of the First Japan-New Zealand Workshop on Logic in Computer Science, special issue editors D.S. Bridges, C.S. Calude, M.J. Dinneen and B. Khoussainov
Supplemental Papers for the 2nd Unconventional Models of Computation Conference
No full textThese are additional papers of talks that were presented at the Second International
Conference on Unconventional Models of Computation (UMC’2K).
UMC’2K, organized by the Centre for Discrete Mathematics and Theoretical
Computer Science, the International Solvay Institutes for Physics and Chemistry
and the Vrije Universiteit Brussel Theoretical Physics Division was held
at Solvay Institutes during December 13–16, 2000.
The conference encompasses all areas of unconventional computation, especially
quantum computing, DNA-based computation, evolutionary algorithms
and other proposals for computation models that go beyond the Turing model.
Additional refereed and invited papers of UMC’2K appear in the following proceedings:
I. Antoniou, C. S. Calude, M. J. Dinneen, editors. Unconventional
Models of Computation, UMC’2K, Springer-Verlag, London, December
2000, XI + 301 pages
C.S. Lewis: Reactions from Women
Get PDFRecounts the experiences of eight women (including the author) who knew C.S. Lewis
- …
