<?xml version="1.0" encoding="UTF-8"?>
<!DOCTYPE article PUBLIC "-//TaxonX//DTD Taxonomic Treatment Publishing DTD v0 20100105//EN" "../../nlm/tax-treatment-NS0.dtd">
<article xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:tp="http://www.plazi.org/taxpub" article-type="research-article" dtd-version="3.0" xml:lang="en">
  <front>
    <journal-meta>
      <journal-id journal-id-type="publisher-id">109</journal-id>
      <journal-id journal-id-type="index">urn:lsid:arphahub.com:pub:3dc5f44e-8666-58db-bc76-a455210e8891</journal-id>
      <journal-title-group>
        <journal-title xml:lang="en">JUCS - Journal of Universal Computer Science</journal-title>
        <abbrev-journal-title xml:lang="en">jucs</abbrev-journal-title>
      </journal-title-group>
      <issn pub-type="ppub">0948-695X</issn>
      <issn pub-type="epub">0948-6968</issn>
      <publisher>
        <publisher-name>Journal of Universal Computer Science</publisher-name>
      </publisher>
    </journal-meta>
    <article-meta>
      <article-id pub-id-type="doi">10.3897/jucs.69617</article-id>
      <article-id pub-id-type="publisher-id">69617</article-id>
      <article-categories>
        <subj-group subj-group-type="heading">
          <subject>Research Article</subject>
        </subj-group>
        <subj-group subj-group-type="scientific_subject">
          <subject>B.2 - ARITHMETIC AND LOGIC STRUCTURES</subject>
          <subject>B.6 - LOGIC DESIGN</subject>
          <subject>F.1 - COMPUTATION BY ABSTRACT DEVICES</subject>
          <subject>F.2 - ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY</subject>
        </subj-group>
      </article-categories>
      <title-group>
        <article-title>A reversible circuit synthesis algorithm with progressive increase of controls in generalized Toffoli gates</article-title>
      </title-group>
      <contrib-group content-type="authors">
        <contrib contrib-type="author" corresp="no">
          <name name-style="western">
            <surname>Dalcumune</surname>
            <given-names>Edinelço</given-names>
          </name>
          <xref ref-type="aff" rid="A1">1</xref>
        </contrib>
        <contrib contrib-type="author" corresp="no">
          <name name-style="western">
            <surname>Antonio Brasil Kowada</surname>
            <given-names>Luis</given-names>
          </name>
          <xref ref-type="aff" rid="A2">2</xref>
        </contrib>
        <contrib contrib-type="author" corresp="no">
          <name name-style="western">
            <surname>da Cunha Ribeiro</surname>
            <given-names>André</given-names>
          </name>
          <xref ref-type="aff" rid="A3">3</xref>
        </contrib>
        <contrib contrib-type="author" corresp="no">
          <name name-style="western">
            <surname>Miraglia Herrera de Figueiredo</surname>
            <given-names>Celina</given-names>
          </name>
          <xref ref-type="aff" rid="A4">4</xref>
        </contrib>
        <contrib contrib-type="author" corresp="yes">
          <name name-style="western">
            <surname>de Lima Marquezino</surname>
            <given-names>Franklin</given-names>
          </name>
          <email xlink:type="simple">franklin@cos.ufrj.br</email>
          <xref ref-type="aff" rid="A4">4</xref>
        </contrib>
      </contrib-group>
      <aff id="A1">
        <label>1</label>
        <addr-line content-type="verbatim">Universidade Federal dos Vales do Jequitinhonha e Mucuri, Teófilo Otoni, Brazil</addr-line>
        <institution>Universidade Federal dos Vales do Jequitinhonha e Mucuri</institution>
        <addr-line content-type="city">Teófilo Otoni</addr-line>
        <country>Brazil</country>
      </aff>
      <aff id="A2">
        <label>2</label>
        <addr-line content-type="verbatim">Universidade Federal Fluminense, Niteroi, Brazil</addr-line>
        <institution>Universidade Federal Fluminense</institution>
        <addr-line content-type="city">Niteroi</addr-line>
        <country>Brazil</country>
      </aff>
      <aff id="A3">
        <label>3</label>
        <addr-line content-type="verbatim">Instituto Federal Goiano, Goiás, Brazil</addr-line>
        <institution>Instituto Federal Goiano</institution>
        <addr-line content-type="city">Goiás</addr-line>
        <country>Brazil</country>
      </aff>
      <aff id="A4">
        <label>4</label>
        <addr-line content-type="verbatim">Universidade Federal do Rio de Janeiro, Rio de Janeiro, Brazil</addr-line>
        <institution>Universidade Federal do Rio de Janeiro</institution>
        <addr-line content-type="city">Rio de Janeiro</addr-line>
        <country>Brazil</country>
      </aff>
      <author-notes>
        <fn fn-type="corresp">
          <p>Corresponding author: Franklin de Lima Marquezino (<email xlink:type="simple">franklin@cos.ufrj.br</email>).</p>
        </fn>
        <fn fn-type="edited-by">
          <p>Academic editor: </p>
        </fn>
      </author-notes>
      <pub-date pub-type="collection">
        <year>2021</year>
      </pub-date>
      <pub-date pub-type="epub">
        <day>28</day>
        <month>06</month>
        <year>2021</year>
      </pub-date>
      <volume>27</volume>
      <issue>6</issue>
      <fpage>544</fpage>
      <lpage>563</lpage>
      <uri content-type="arpha" xlink:href="http://openbiodiv.net/82EA821B-0094-5338-A461-6DAC8686E8F7">82EA821B-0094-5338-A461-6DAC8686E8F7</uri>
      <uri content-type="zenodo_dep_id" xlink:href="https://zenodo.org/record/5073702">5073702</uri>
      <history>
        <date date-type="received">
          <day>05</day>
          <month>05</month>
          <year>2020</year>
        </date>
        <date date-type="accepted">
          <day>14</day>
          <month>05</month>
          <year>2021</year>
        </date>
      </history>
      <permissions>
        <copyright-statement>Edinelço Dalcumune, Luis Antonio Brasil Kowada, André da Cunha Ribeiro, Celina Miraglia Herrera de Figueiredo, Franklin de Lima Marquezino</copyright-statement>
        <license license-type="creative-commons-attribution" xlink:href="https://creativecommons.org/licenses/by-nd/4.0/" xlink:type="simple">
          <license-p>This is an open access article distributed under the terms of the Creative Commons Attribution License (CC BY-ND 4.0). This license allows reusers to copy and distribute the material in any medium or format in unadapted form only, and only so long as attribution is given to the creator. The license allows for commercial use.</license-p>
        </license>
      </permissions>
      <abstract>
        <label>Abstract</label>
        <p>We present a new algorithm for synthesis of reversible circuits for arbitrary <italic>n</italic>-bit bijective functions. This algorithm uses generalized Toffoli gates, which include positive and negative controls. Our algorithm is divided into two parts. First, we use partially controlled gen- eralized Toffoli gates, progressively increasing the number of controls. Second, exploring the properties of the representation of permutations in disjoint cycles, we apply generalized Toffoli gates with controls on all lines except for the target line. Therefore, new in the method is the fact that the obtained circuits use first low cost gates and consider increasing costs towards the end of the synthesis. In addition, we employ two bidirectional synthesis strategies to improve the gate count, which is the metric used to compare the results obtained by our algorithm with the results presented in the literature. Accordingly, our experimental results consider all 3-bit bijective functions and twenty widely used benchmark functions. The results obtained by our synthesis algorithm are competitive when compared with the best results known in the literature, considering as a complexity metric just the number of gates, as done by alternative best heuristics found in the literature. For example, for all 3-bit bijective functions using generalized Toffoli gates library, we obtained the best so far average count of 5<italic>.</italic>23.</p>
      </abstract>
      <funding-group>
        <award-group>
          <funding-source>
            <named-content content-type="funder_name">Coordenação de Aperfeiçoamento de Pessoal de Nível Superior</named-content>
            <named-content content-type="funder_identifier">501100002322</named-content>
            <named-content content-type="funder_doi">http://doi.org/10.13039/501100002322</named-content>
          </funding-source>
        </award-group>
        <award-group>
          <funding-source>
            <named-content content-type="funder_name">Conselho Nacional de Desenvolvimento Científico e Tecnológico</named-content>
            <named-content content-type="funder_identifier">501100003593</named-content>
            <named-content content-type="funder_doi">http://doi.org/10.13039/501100003593</named-content>
          </funding-source>
        </award-group>
        <award-group>
          <funding-source>
            <named-content content-type="funder_name">Fundação Carlos Chagas Filho de Amparo à Pesquisa do Estado do Rio de Janeiro</named-content>
            <named-content content-type="funder_identifier">501100004586</named-content>
            <named-content content-type="funder_doi">http://doi.org/10.13039/501100004586</named-content>
          </funding-source>
        </award-group>
      </funding-group>
    </article-meta>
  </front>
</article>
