Contributions to Conferences

back

Canonical Multi-target Toffoli Circuits


Authors

  • Kreowski, H.-J.
  • Kuske, S.
  • Lye, A.

Meta information [BibTeX]

  • Year: 2016, Reviewed
  • Dediu, A.-H. and Janoušek, J. and Martín-Vide, C. and Truthe, B. (Editors)
  • In: Language and Automata Theory and Applications
  • Subtitle: 10th International Conference, LATA 2016, Prague, Czech Republic, March 14-18, 2016, Proceedings
  • Conference: LATA 2016 in Prague, Czech Republic (March 14-18, 2016)
  • Series: Lecture Notes in Computer Science, Vol. 9618
  • Publisher: Springer International Publishing
  • Pages: 603-616
  • ISBN: 978-3-319-29999-0, eISBN: 978-3-319-30000-9
  • ISSN: 0302-9743
  • DOI: 10.1007/978-3-319-30000-9_46



Arbeitsgruppe Theoretical Computer Science


Abstract

In this paper, we study reversible circuits as cascades of multi-target Toffoli gates. This new type of gates allows to shift parts of a gate to the preceding gate within a circuit provided that a certain independence condition holds. It turns out that shifts decrease the so-called waiting degree such that shifting as long as possible always terminates and yields shift-reduced circuits. As the main result, we show that shift-reduced circuits are unique canonical representatives of their shift equivalence classes. Canonical circuits are optimal with respect to maximal and as-early-as-possible parallelism of targets within gates.



Kreowski, H.-J.; Kuske, S.; Lye, A.
Canonical Multi-target Toffoli Circuits
In: Dediu, A.-H.; Janoušek, J.; Martín-Vide, C.; Truthe, B. (eds.): Language and Automata Theory and Applications. 10th International Conference, LATA 2016, Prague, Czech Republic, March 14-18, 2016, Proceedings. Springer International Publishing, 2016, pp. 603-616
(Workgroup: Theoretical Computer Science)
BibTeX Close


Download as .bib