6 Search Results for "Evans, William"


Document
Reversible Bond Logic

Authors: Hannah Amelie Earley

Published in: LIPIcs, Volume 276, 29th International Conference on DNA Computing and Molecular Programming (DNA 29) (2023)


Abstract
The field of molecular programming allows for the programming of the structure and behavior of matter at the molecular level, even to the point of encoding arbitrary computation. However, current approaches tend to be wasteful in terms of monomers, gate complexes, and free energy. In response, we present a novel abstract model of molecular programming, Reversible Bond Logic (RBL), which exploits the concepts of reversibility and reversible computing to help address these issues. RBL systems permit very general manipulations of arbitrarily complex "molecular" structures, and possess properties such as component reuse, modularity, compositionality. We will demonstrate the implementation of a common free-energy currency that can be shared across systems, initially using it to power a biased walker. Then we will introduce some basic motifs for the manipulation of structures, which will be used to implement such computational primitives as conditional branching, looping, and subroutines. Example programs will include logical negation, and addition and squaring of arbitrarily large numbers. As a consequence of reversibility, we will also obtain the inverse programs (subtraction and square-rooting) for free. Due to modularity, multiple instances of these computations can occur in parallel without cross-talk. Future work aims to further characterize RBL, and develop variants that may be amenable to experimental implementation.

Cite as

Hannah Amelie Earley. Reversible Bond Logic. In 29th International Conference on DNA Computing and Molecular Programming (DNA 29). Leibniz International Proceedings in Informatics (LIPIcs), Volume 276, pp. 6:1-6:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{earley:LIPIcs.DNA.29.6,
  author =	{Earley, Hannah Amelie},
  title =	{{Reversible Bond Logic}},
  booktitle =	{29th International Conference on DNA Computing and Molecular Programming (DNA 29)},
  pages =	{6:1--6:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-297-6},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{276},
  editor =	{Chen, Ho-Lin and Evans, Constantine G.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DNA.29.6},
  URN =		{urn:nbn:de:0030-drops-187893},
  doi =		{10.4230/LIPIcs.DNA.29.6},
  annote =	{Keywords: Molecular Programming, Reversible Computing, Structural Manipulation}
}
Document
Recognizing a DOG is Hard, But Not When It is Thin and Unit

Authors: William Evans, Mereke van Garderen, Maarten Löffler, and Valentin Polishchuk

Published in: LIPIcs, Volume 49, 8th International Conference on Fun with Algorithms (FUN 2016)


Abstract
We define the notion of disk-obedience for a set of disks in the plane and give results for diskobedient graphs (DOGs), which are disk intersection graphs (DIGs) that admit a planar embedding with vertices inside the corresponding disks. We show that in general it is hard to recognize a DOG, but when the DIG is thin and unit (i.e., when the disks are unit disks), it can be done in linear time.

Cite as

William Evans, Mereke van Garderen, Maarten Löffler, and Valentin Polishchuk. Recognizing a DOG is Hard, But Not When It is Thin and Unit. In 8th International Conference on Fun with Algorithms (FUN 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 49, pp. 16:1-16:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)


Copy BibTex To Clipboard

@InProceedings{evans_et_al:LIPIcs.FUN.2016.16,
  author =	{Evans, William and van Garderen, Mereke and L\"{o}ffler, Maarten and Polishchuk, Valentin},
  title =	{{Recognizing a DOG is Hard, But Not When It is Thin and Unit}},
  booktitle =	{8th International Conference on Fun with Algorithms (FUN 2016)},
  pages =	{16:1--16:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-005-7},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{49},
  editor =	{Demaine, Erik D. and Grandoni, Fabrizio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2016.16},
  URN =		{urn:nbn:de:0030-drops-58671},
  doi =		{10.4230/LIPIcs.FUN.2016.16},
  annote =	{Keywords: graph drawing, planar graphs, disk intersection graphs}
}
Document
Clone Detection via Structural Abstraction

Authors: William S. Evans, Christoph W. Fraser, and Fei Ma

Published in: Dagstuhl Seminar Proceedings, Volume 8261, Structure-Based Compression of Complex Massive Data (2008)


Abstract
This paper describes the design, implementation, and application of a new algorithm to detect cloned code. It operates on the abstract syntax trees formed by many compilers as an intermediate representation. It extends prior work by identifying clones even when arbitrary subtrees have been changed. On a 440,000-line code corpus, 20- 50%of the clones it detected were missed by previous methods. The method also identifies cloning in declarations, so it is somewhat more general than conventional procedural abstraction.

Cite as

William S. Evans, Christoph W. Fraser, and Fei Ma. Clone Detection via Structural Abstraction. In Structure-Based Compression of Complex Massive Data. Dagstuhl Seminar Proceedings, Volume 8261, pp. 1-10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)


Copy BibTex To Clipboard

@InProceedings{evans_et_al:DagSemProc.08261.7,
  author =	{Evans, William S. and Fraser, Christoph W. and Ma, Fei},
  title =	{{Clone Detection via Structural Abstraction}},
  booktitle =	{Structure-Based Compression of Complex Massive Data},
  pages =	{1--10},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8261},
  editor =	{Stefan B\"{o}ttcher and Markus Lohrey and Sebastian Maneth and Wojcieh Rytter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.08261.7},
  URN =		{urn:nbn:de:0030-drops-16784},
  doi =		{10.4230/DagSemProc.08261.7},
  annote =	{Keywords: Clone Detection}
}
Document
06301 Working Session Summary: Presentation and Visualization of Redundant Code

Authors: Andrew Walenstein, James R. Cordy, William S. Evans, Ahmed Hassan, Toshihiro Kamiya, Cory Kapser, and Ettore Merlo

Published in: Dagstuhl Seminar Proceedings, Volume 6301, Duplication, Redundancy, and Similarity in Software (2007)


Abstract
This report summarizes the proceedings of a workshop discussion session presentation and visualization of aspects relating to duplicated, copied, or cloned code. The main outcomes of the working session were: (a) a realization that two researchers had independently generated very similar methods for browsing and visualization clone "clusters," and (b) a list of questions for visualization, particularly in relation to how the "proximity" of clones may relate to interest in the clone.

Cite as

Andrew Walenstein, James R. Cordy, William S. Evans, Ahmed Hassan, Toshihiro Kamiya, Cory Kapser, and Ettore Merlo. 06301 Working Session Summary: Presentation and Visualization of Redundant Code. In Duplication, Redundancy, and Similarity in Software. Dagstuhl Seminar Proceedings, Volume 6301, pp. 1-5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)


Copy BibTex To Clipboard

@InProceedings{walenstein_et_al:DagSemProc.06301.3,
  author =	{Walenstein, Andrew and Cordy, James R. and Evans, William S. and Hassan, Ahmed and Kamiya, Toshihiro and Kapser, Cory and Merlo, Ettore},
  title =	{{06301 Working Session Summary: Presentation and Visualization of Redundant Code}},
  booktitle =	{Duplication, Redundancy, and Similarity in Software},
  pages =	{1--5},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{6301},
  editor =	{Rainer Koschke and Ettore Merlo and Andrew Walenstein},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.06301.3},
  URN =		{urn:nbn:de:0030-drops-9661},
  doi =		{10.4230/DagSemProc.06301.3},
  annote =	{Keywords: Code clone, clone visualization, presentation, software visualization}
}
Document
Program Compression

Authors: William S. Evans

Published in: Dagstuhl Seminar Proceedings, Volume 6301, Duplication, Redundancy, and Similarity in Software (2007)


Abstract
The talk focused on a grammar-based technique for identifying redundancy in program code and taking advantage of that redundancy to reduce the memory required to store and execute the program. The idea is to start with a simple context-free grammar that represents all valid basic blocks of any program. We represent a program by the parse trees (i.e. derivations) of its basic blocks using the grammar. We then modify the grammar, by considering sample programs, so that idioms of the language have shorter derivations in the modified grammar. Since each derivation represents a basic block, we can interpret the resulting set of derivations much as we would interpret the original program. We need only expand the grammar rules indicated by the derivation to produce a sequence of original program instructions to execute. The result is a program representation that is approximately 40% of the original program size and is interpretable by a very modest-sized interpreter.

Cite as

William S. Evans. Program Compression. In Duplication, Redundancy, and Similarity in Software. Dagstuhl Seminar Proceedings, Volume 6301, pp. 1-10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)


Copy BibTex To Clipboard

@InProceedings{evans:DagSemProc.06301.10,
  author =	{Evans, William S.},
  title =	{{Program Compression}},
  booktitle =	{Duplication, Redundancy, and Similarity in Software},
  pages =	{1--10},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{6301},
  editor =	{Rainer Koschke and Ettore Merlo and Andrew Walenstein},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.06301.10},
  URN =		{urn:nbn:de:0030-drops-9635},
  doi =		{10.4230/DagSemProc.06301.10},
  annote =	{Keywords: Program compression, clone detection, bytecode interpretation, variable-to-fixed length codes, context-free grammars}
}
Document
Similarity in Programs

Authors: Andrew Walenstein, Mohammad El-Ramly, James R. Cordy, William S. Evans, Kiarash Mahdavi, Markus Pizka, Ganesan Ramalingam, and Jürgen Wolff von Gudenberg

Published in: Dagstuhl Seminar Proceedings, Volume 6301, Duplication, Redundancy, and Similarity in Software (2007)


Abstract
An overview of the concept of program similarity is presented. It divides similarity into two types - syntactic and semantic - and provides a review of eight categories of methods that may be used to measure program similarity. A summary of some applications of these methods is included. The paper is intended to be a starting point for a more comprehensive analysis of the subject of similarity in programs, which is critical to understand if progress is to be made in fields such as clone detection.

Cite as

Andrew Walenstein, Mohammad El-Ramly, James R. Cordy, William S. Evans, Kiarash Mahdavi, Markus Pizka, Ganesan Ramalingam, and Jürgen Wolff von Gudenberg. Similarity in Programs. In Duplication, Redundancy, and Similarity in Software. Dagstuhl Seminar Proceedings, Volume 6301, pp. 1-8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)


Copy BibTex To Clipboard

@InProceedings{walenstein_et_al:DagSemProc.06301.11,
  author =	{Walenstein, Andrew and El-Ramly, Mohammad and Cordy, James R. and Evans, William S. and Mahdavi, Kiarash and Pizka, Markus and Ramalingam, Ganesan and von Gudenberg, J\"{u}rgen Wolff},
  title =	{{Similarity in Programs}},
  booktitle =	{Duplication, Redundancy, and Similarity in Software},
  pages =	{1--8},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{6301},
  editor =	{Rainer Koschke and Ettore Merlo and Andrew Walenstein},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.06301.11},
  URN =		{urn:nbn:de:0030-drops-9681},
  doi =		{10.4230/DagSemProc.06301.11},
  annote =	{Keywords: Computer programs, similarity, code clone, software comparison, program metrics, Levenshtein distance, parameterized difference, feature space, shared}
}
  • Refine by Author
  • 4 Evans, William S.
  • 2 Cordy, James R.
  • 2 Walenstein, Andrew
  • 1 Earley, Hannah Amelie
  • 1 El-Ramly, Mohammad
  • Show More...

  • Refine by Classification
  • 1 Computer systems organization → Molecular computing
  • 1 Theory of computation → Models of computation

  • Refine by Keyword
  • 1 Clone Detection
  • 1 Code clone
  • 1 Computer programs
  • 1 Levenshtein distance
  • 1 Molecular Programming
  • Show More...

  • Refine by Type
  • 6 document

  • Refine by Publication Year
  • 3 2007
  • 1 2008
  • 1 2016
  • 1 2023

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail