Search

Your search keyword '"Simonsen, Jakob Grue"' showing total 5 results
Start Over Author "Simonsen, Jakob Grue" Database Supplemental Index
5 results on '"Simonsen, Jakob Grue"'

1. On Beta-Shifts Having Arithmetical Languages.

Author

Jedrzejowicz, Joanna, Szepietowski, Andrzej, and Simonsen, Jakob Grue

Abstract

Let β be a real number with 1 < β < 2. We prove that the language of the β-shift is Δ0n iff β is a Δn-real. The special case where n is 1 is the independently interesting result that the language of the β-shift is decidable iff β is a computable real. The "if" part of the proof is non-constructive; we show that for Walters' version of the β-shift, no constructive proof exists. [ABSTRACT FROM AUTHOR]

Published
2005
Full Text
View/download PDF

2. On Confluence of Infinitary Combinatory Reduction Systems.

Author

Sutcliffe, Geoff, Voronkov, Andrei, Ketema, Jeroen, and Simonsen, Jakob Grue

Abstract

We prove that fully-extended, orthogonal infinitary combinatory reduction systems with finite right-hand sides are confluent modulo identification of hypercollapsing subterms. This provides the first general confluence result for infinitary higher-order rewriting. [ABSTRACT FROM AUTHOR]

Published
2005
Full Text
View/download PDF

3. Infinitary Combinatory Reduction Systems.

Author

Giesl, Jürgen, Ketema, Jeroen, and Simonsen, Jakob Grue

Abstract

We define infinitary combinatory reduction systems (iCRSs). This provides the first extension of infinitary rewriting to higher-order rewriting. We lift two well-known results from infinitary term rewriting systems and infinitary λ-calculus to iCRSs: 1every reduction sequence in a fully-extended left-linear iCRS is compressible to a reduction sequence of length at most ω, and 2every complete development of the same set of redexes in an orthogonal iCRS ends in the same term. [ABSTRACT FROM AUTHOR]

Published
2005

4. Programming in Biomolecular Computation: Programs, Self-Interpretation and Visualisation.

Author

HARTMANN, Lars, JONES, Neil D., SIMONSEN, Jakob Grue, and VRIST, Søren Bjerregaard

Subjects
BIOLOGICALLY inspired computing, ALGORITHMS, COMPUTER programming, COMPUTER simulation, TURING machines
Abstract

Our goal is to provide a top-down approach to biomolecular computation. In spite of widespread discussion about connections between biology and computation, one question seems notable by its absence: Where are the programs? We identify a number of common features in programming that seem conspicuously absent from the literature on biomolecular computing; to partially redress this absence, we introduce a model of computation that is evidently programmable, by programs reminiscent of low-level computer machine code; and at the same time biologically plausible: its functioning is defined by a single and relatively small set of chemical-like reaction rules. Further properties: the model is stored-program: programs are the same as data, so programs are not only executable, but are also compilable and interpretable. It is universal: all computable functions can be computed (in natural ways and without arcane encodings of data and algorithm); it is also uniform: new \hardware" is not needed to solve new problems; and (last but not least) it is Turing complete in a strong sense: a universal algorithm exists, that is able to execute any program, and is not asymptotically inefficient. [ABSTRACT FROM AUTHOR]

Published
2011

5. Programming in Biomolecular Computation.

Author

Hartmann, Lars, Jones, Neil D., and Simonsen, Jakob Grue

Subjects
COMPUTATIONAL biology, BIOMOLECULES, COMPUTABLE functions, ALGORITHMS, CHEMICAL reactions, COMPUTER programming
Abstract

Abstract: Our goal is to provide a top-down approach to biomolecular computation. In spite of widespread discussion about connections between biology and computation, one question seems notable by its absence: Where are the programs? We introduce a model of computation that is evidently programmable, by programs reminiscent of low-level computer machine code; and at the same time biologically plausible: its functioning is defined by a single and relatively small set of chemical-like reaction rules. Further properties: the model is stored-program: programs are the same as data, so programs are not only executable, but are also compilable and interpretable. It is universal: all computable functions can be computed (in natural ways and without arcane encodings of data and algorithm); it is also uniform: new “hardware” is not needed to solve new problems; and (last but not least) it is Turing complete in a strong sense: a universal algorithm exists, that is able to execute any program, and is not asymptotically inefficient. A prototype model has been implemented (for now in silico on a conventional computer). This work opens new perspectives on just how computation may be specified at the biological level. [Copyright &y& Elsevier]

Published
2010
Full Text
View/download PDF

Catalog

Books, media, physical & digital resources
See catalog results