<?xml version="1.0" encoding="utf-8"?>
<TEI xmlns="http://www.tei-c.org/ns/1.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns:hal="http://hal.archives-ouvertes.fr/" xmlns:gml="http://www.opengis.net/gml/3.3/" xmlns:gmlce="http://www.opengis.net/gml/3.3/ce" version="1.1" xsi:schemaLocation="http://www.tei-c.org/ns/1.0 http://api.archives-ouvertes.fr/documents/aofr-sword.xsd">
  <teiHeader>
    <fileDesc>
      <titleStmt>
        <title>HAL TEI export of hal-02290400</title>
      </titleStmt>
      <publicationStmt>
        <distributor>CCSD</distributor>
        <availability status="restricted">
          <licence target="https://creativecommons.org/publicdomain/zero/1.0/">CC0 1.0 - Universal</licence>
        </availability>
        <date when="2026-05-02T23:20:19+02:00"/>
      </publicationStmt>
      <sourceDesc>
        <p part="N">HAL API Platform</p>
      </sourceDesc>
    </fileDesc>
  </teiHeader>
  <text>
    <body>
      <listBibl>
        <biblFull>
          <titleStmt>
            <title xml:lang="en">Parameterized verification of algorithms for oblivious robots on a ring</title>
            <author role="aut">
              <persName>
                <forename type="first">Arnaud</forename>
                <surname>Sangnier</surname>
              </persName>
              <email type="md5">492b1216802181586098a2d7020176bb</email>
              <email type="domain">irif.fr</email>
              <idno type="idhal" notation="string">arnaud-sangnier</idno>
              <idno type="idhal" notation="numeric">1118879</idno>
              <idno type="halauthorid" notation="string">386582-1118879</idno>
              <idno type="ARXIV">https://arxiv.org/a/sangnier_a_1</idno>
              <affiliation ref="#struct-444497"/>
            </author>
            <author role="aut">
              <persName>
                <forename type="first">Nathalie</forename>
                <surname>Sznajder</surname>
              </persName>
              <email type="md5">1985896964d5af0fd10729cdf4254541</email>
              <email type="domain">lip6.fr</email>
              <idno type="idhal" notation="string">sznajder-nathalie</idno>
              <idno type="idhal" notation="numeric">5709</idno>
              <idno type="halauthorid" notation="string">26304-5709</idno>
              <idno type="IDREF">https://www.idref.fr/253130883</idno>
              <idno type="ORCID">https://orcid.org/0000-0002-4199-2443</idno>
              <idno type="VIAF">https://viaf.org/viaf/131161512225870562501</idno>
              <affiliation ref="#struct-541717"/>
            </author>
            <author role="aut">
              <persName>
                <forename type="first">Maria</forename>
                <surname>Potop-Butucaru</surname>
              </persName>
              <email type="md5">574e9e606d52567225fb1793a5155253</email>
              <email type="domain">lip6.fr</email>
              <idno type="idhal" notation="numeric">841868</idno>
              <idno type="halauthorid" notation="string">390618-841868</idno>
              <idno type="ORCID">https://orcid.org/0000-0001-6488-8326</idno>
              <idno type="IDREF">https://www.idref.fr/157868869</idno>
              <idno type="VIAF">https://viaf.org/viaf/313539623</idno>
              <idno type="RESEARCHERID">http://www.researcherid.com/rid/FRU-0557-2022</idno>
              <idno type="RESEARCHERID">http://www.researcherid.com/rid/http://www.researcherid.com/rid/FRU-0557-2022</idno>
              <affiliation ref="#struct-541705"/>
            </author>
            <author role="aut">
              <persName>
                <forename type="first">Sébastien</forename>
                <surname>Tixeuil</surname>
              </persName>
              <email type="md5">46fb30964edb44afa6b5deecf5f673eb</email>
              <email type="domain">lip6.fr</email>
              <idno type="idhal" notation="string">tixeuil</idno>
              <idno type="idhal" notation="numeric">9380</idno>
              <idno type="halauthorid" notation="string">5657-9380</idno>
              <idno type="ORCID">https://orcid.org/0000-0002-0948-7172</idno>
              <idno type="IDREF">https://www.idref.fr/121380661</idno>
              <affiliation ref="#struct-541705"/>
            </author>
            <editor role="depositor">
              <persName>
                <forename>Nathalie</forename>
                <surname>Sznajder</surname>
              </persName>
              <email type="md5">1985896964d5af0fd10729cdf4254541</email>
              <email type="domain">lip6.fr</email>
            </editor>
            <funder ref="#projanr-50500"/>
            <funder ref="#projanr-53645"/>
          </titleStmt>
          <editionStmt>
            <edition n="v1" type="current">
              <date type="whenSubmitted">2019-09-17 15:58:29</date>
              <date type="whenModified">2024-10-30 13:33:05</date>
              <date type="whenReleased">2019-09-17 15:58:29</date>
              <date type="whenProduced">2020-12</date>
              <ref type="externalLink" target="http://arxiv.org/pdf/1706.05193"/>
            </edition>
            <respStmt>
              <resp>contributor</resp>
              <name key="324763">
                <persName>
                  <forename>Nathalie</forename>
                  <surname>Sznajder</surname>
                </persName>
                <email type="md5">1985896964d5af0fd10729cdf4254541</email>
                <email type="domain">lip6.fr</email>
              </name>
            </respStmt>
          </editionStmt>
          <publicationStmt>
            <distributor>CCSD</distributor>
            <idno type="halId">hal-02290400</idno>
            <idno type="halUri">https://hal.sorbonne-universite.fr/hal-02290400</idno>
            <idno type="halBibtex">sangnier:hal-02290400</idno>
            <idno type="halRefHtml">&lt;i&gt;Formal Methods in System Design&lt;/i&gt;, 2020, 56, pp.55-89. &lt;a target="_blank" href="https://dx.doi.org/10.1007/s10703-019-00335-y"&gt;&amp;#x27E8;10.1007/s10703-019-00335-y&amp;#x27E9;&lt;/a&gt;</idno>
            <idno type="halRef">Formal Methods in System Design, 2020, 56, pp.55-89. &amp;#x27E8;10.1007/s10703-019-00335-y&amp;#x27E9;</idno>
            <availability status="restricted"/>
          </publicationStmt>
          <seriesStmt>
            <idno type="stamp" n="CNRS">CNRS - Centre national de la recherche scientifique</idno>
            <idno type="stamp" n="LIP6" corresp="SORBONNE-UNIVERSITE">Laboratoire d'Informatique de Paris 6</idno>
            <idno type="stamp" n="SORBONNE-UNIVERSITE">Sorbonne Université</idno>
            <idno type="stamp" n="SORBONNE-UNIV" corresp="SORBONNE-UNIVERSITE">Sorbonne Université 01/01/2018</idno>
            <idno type="stamp" n="SU-SCIENCES" corresp="SORBONNE-UNIVERSITE">Faculté des Sciences de Sorbonne Université</idno>
            <idno type="stamp" n="UNIV-PARIS">Université Paris Cité</idno>
            <idno type="stamp" n="UNIVERSITE-PARIS" corresp="UNIV-PARIS">Université Paris Cité</idno>
            <idno type="stamp" n="UP-SCIENCES">Université Paris Cité - Faculté des Sciences</idno>
            <idno type="stamp" n="TEST-HALCNRS">Collection test HAL CNRS</idno>
            <idno type="stamp" n="SU-TI">Sorbonne Université - Texte Intégral</idno>
            <idno type="stamp" n="ANR">ANR</idno>
            <idno type="stamp" n="ALLIANCE-SU"> Alliance Sorbonne Université</idno>
            <idno type="stamp" n="IRIF">Institut de Recherche en Informatique Fondamentale</idno>
            <idno type="stamp" n="SPRES">Séminaires Parisiens en Réseaux</idno>
            <idno type="stamp" n="SUPRA_MATHS_INFO">Mathématiques + Informatique</idno>
          </seriesStmt>
          <notesStmt>
            <note type="audience" n="2">International</note>
            <note type="popular" n="0">No</note>
            <note type="peer" n="1">Yes</note>
          </notesStmt>
          <sourceDesc>
            <biblStruct>
              <analytic>
                <title xml:lang="en">Parameterized verification of algorithms for oblivious robots on a ring</title>
                <author role="aut">
                  <persName>
                    <forename type="first">Arnaud</forename>
                    <surname>Sangnier</surname>
                  </persName>
                  <email type="md5">492b1216802181586098a2d7020176bb</email>
                  <email type="domain">irif.fr</email>
                  <idno type="idhal" notation="string">arnaud-sangnier</idno>
                  <idno type="idhal" notation="numeric">1118879</idno>
                  <idno type="halauthorid" notation="string">386582-1118879</idno>
                  <idno type="ARXIV">https://arxiv.org/a/sangnier_a_1</idno>
                  <affiliation ref="#struct-444497"/>
                </author>
                <author role="aut">
                  <persName>
                    <forename type="first">Nathalie</forename>
                    <surname>Sznajder</surname>
                  </persName>
                  <email type="md5">1985896964d5af0fd10729cdf4254541</email>
                  <email type="domain">lip6.fr</email>
                  <idno type="idhal" notation="string">sznajder-nathalie</idno>
                  <idno type="idhal" notation="numeric">5709</idno>
                  <idno type="halauthorid" notation="string">26304-5709</idno>
                  <idno type="IDREF">https://www.idref.fr/253130883</idno>
                  <idno type="ORCID">https://orcid.org/0000-0002-4199-2443</idno>
                  <idno type="VIAF">https://viaf.org/viaf/131161512225870562501</idno>
                  <affiliation ref="#struct-541717"/>
                </author>
                <author role="aut">
                  <persName>
                    <forename type="first">Maria</forename>
                    <surname>Potop-Butucaru</surname>
                  </persName>
                  <email type="md5">574e9e606d52567225fb1793a5155253</email>
                  <email type="domain">lip6.fr</email>
                  <idno type="idhal" notation="numeric">841868</idno>
                  <idno type="halauthorid" notation="string">390618-841868</idno>
                  <idno type="ORCID">https://orcid.org/0000-0001-6488-8326</idno>
                  <idno type="IDREF">https://www.idref.fr/157868869</idno>
                  <idno type="VIAF">https://viaf.org/viaf/313539623</idno>
                  <idno type="RESEARCHERID">http://www.researcherid.com/rid/FRU-0557-2022</idno>
                  <idno type="RESEARCHERID">http://www.researcherid.com/rid/http://www.researcherid.com/rid/FRU-0557-2022</idno>
                  <affiliation ref="#struct-541705"/>
                </author>
                <author role="aut">
                  <persName>
                    <forename type="first">Sébastien</forename>
                    <surname>Tixeuil</surname>
                  </persName>
                  <email type="md5">46fb30964edb44afa6b5deecf5f673eb</email>
                  <email type="domain">lip6.fr</email>
                  <idno type="idhal" notation="string">tixeuil</idno>
                  <idno type="idhal" notation="numeric">9380</idno>
                  <idno type="halauthorid" notation="string">5657-9380</idno>
                  <idno type="ORCID">https://orcid.org/0000-0002-0948-7172</idno>
                  <idno type="IDREF">https://www.idref.fr/121380661</idno>
                  <affiliation ref="#struct-541705"/>
                </author>
              </analytic>
              <monogr>
                <idno type="halJournalId" status="VALID">13429</idno>
                <idno type="issn">0925-9856</idno>
                <idno type="eissn">1572-8102</idno>
                <title level="j">Formal Methods in System Design</title>
                <imprint>
                  <publisher>Springer Verlag</publisher>
                  <biblScope unit="volume">56</biblScope>
                  <biblScope unit="pp">55-89</biblScope>
                  <date type="datePub">2020-12</date>
                  <date type="dateEpub">2019-07-30</date>
                </imprint>
              </monogr>
              <idno type="arxiv">1706.05193</idno>
              <idno type="doi">10.1007/s10703-019-00335-y</idno>
            </biblStruct>
          </sourceDesc>
          <profileDesc>
            <langUsage>
              <language ident="en">English</language>
            </langUsage>
            <textClass>
              <classCode scheme="halDomain" n="info.info-lo">Computer Science [cs]/Logic in Computer Science [cs.LO]</classCode>
              <classCode scheme="halDomain" n="info.info-fl">Computer Science [cs]/Formal Languages and Automata Theory [cs.FL]</classCode>
              <classCode scheme="halTypology" n="ART">Journal articles</classCode>
              <classCode scheme="halOldTypology" n="ART">Journal articles</classCode>
              <classCode scheme="halTreeTypology" n="ART">Journal articles</classCode>
            </textClass>
            <abstract xml:lang="en">
              <p>We study verification problems for autonomous swarms of mobile robots that self-organize and cooperate to solve global objectives. In particular, we focus in this paper on the model proposed by Suzuki and Yamashita of anonymous robots evolving in a discrete space with a finite number of locations (here, a ring). A large number of algorithms have been proposed working for rings whose size is not a priori fixed and can be hence considered as a parameter. Handmade correctness proofs of these algorithms have been shown to be error-prone, and recent attention had been given to the application of formal methods to automatically prove those. Our work is the first to study the verification problem of such algorithms in the parameterized case. We show that safety and reachability problems are undecidable for robots evolving asynchronously. On the positive side, we show that safety properties are decidable in the synchronous case, as well as in the asynchronous case for a particular class of algorithms. Several other properties of the protocol can be decided as well. Decision procedures rely on an encoding in Presburger arithmetics formulae that can be verified by an SMT-solver. Feasibility of our approach is demonstrated by the encoding of several case studies.</p>
            </abstract>
          </profileDesc>
        </biblFull>
      </listBibl>
    </body>
    <back>
      <listOrg type="structures">
        <org type="laboratory" xml:id="struct-444497" status="OLD">
          <idno type="IdRef">193993007</idno>
          <idno type="RNSR">201621976X</idno>
          <orgName>Institut de Recherche en Informatique Fondamentale</orgName>
          <orgName type="acronym">IRIF (UMR_8243)</orgName>
          <date type="start">2016-01-01</date>
          <date type="end">2019-12-31</date>
          <desc>
            <address>
              <addrLine>Université de ParisBâtiment Sophie Germain, Case courrier 70148 Place Aurélie Nemours75205 Paris Cedex 13</addrLine>
              <country key="FR"/>
            </address>
            <ref type="url">https://www.irif.fr/</ref>
          </desc>
          <listRelation>
            <relation name="UMR_8243" active="#struct-300301" type="direct"/>
            <relation name="UMR8243" active="#struct-441569" type="direct"/>
          </listRelation>
        </org>
        <org type="researchteam" xml:id="struct-541717" status="VALID">
          <orgName>Modélisation et Vérification</orgName>
          <orgName type="acronym">MoVe</orgName>
          <date type="start">2018-01-01</date>
          <desc>
            <address>
              <country key="FR"/>
            </address>
          </desc>
          <listRelation>
            <relation active="#struct-541703" type="direct"/>
            <relation active="#struct-413221" type="indirect"/>
            <relation name="UMR7606" active="#struct-441569" type="indirect"/>
          </listRelation>
        </org>
        <org type="researchteam" xml:id="struct-541705" status="VALID">
          <orgName>Networks and Performance Analysis</orgName>
          <orgName type="acronym">NPA</orgName>
          <date type="start">2018-01-01</date>
          <desc>
            <address>
              <country key="FR"/>
            </address>
          </desc>
          <listRelation>
            <relation active="#struct-541703" type="direct"/>
            <relation active="#struct-413221" type="indirect"/>
            <relation name="UMR7606" active="#struct-441569" type="indirect"/>
          </listRelation>
        </org>
        <org type="institution" xml:id="struct-300301" status="OLD">
          <idno type="IdRef">027542084</idno>
          <idno type="ISNI">0000000121514068</idno>
          <idno type="ROR">https://ror.org/02n7qrg46</idno>
          <orgName>Université Paris Diderot - Paris 7</orgName>
          <orgName type="acronym">UPD7</orgName>
          <date type="end">2019-12-31</date>
          <desc>
            <address>
              <addrLine>5 rue Thomas-Mann - 75205 Paris cedex 13</addrLine>
              <country key="FR"/>
            </address>
            <ref type="url">http://www.univ-paris-diderot.fr</ref>
          </desc>
        </org>
        <org type="regroupinstitution" xml:id="struct-441569" status="VALID">
          <idno type="IdRef">02636817X</idno>
          <idno type="ISNI">0000000122597504</idno>
          <idno type="ROR">https://ror.org/02feahw73</idno>
          <orgName>Centre National de la Recherche Scientifique</orgName>
          <orgName type="acronym">CNRS</orgName>
          <date type="start">1939-10-19</date>
          <desc>
            <address>
              <country key="FR"/>
            </address>
            <ref type="url">https://www.cnrs.fr/</ref>
          </desc>
        </org>
        <org type="laboratory" xml:id="struct-541703" status="VALID">
          <idno type="IdRef">13558292X</idno>
          <idno type="RNSR">199712651U</idno>
          <idno type="ROR">https://ror.org/05krcen59</idno>
          <orgName>LIP6</orgName>
          <date type="start">2018-01-01</date>
          <desc>
            <address>
              <addrLine>4 Place JUSSIEU 75252 PARIS CEDEX 05</addrLine>
              <country key="FR"/>
            </address>
            <ref type="url">http://www.lip6.fr/</ref>
          </desc>
          <listRelation>
            <relation active="#struct-413221" type="direct"/>
            <relation name="UMR7606" active="#struct-441569" type="direct"/>
          </listRelation>
        </org>
        <org type="regroupinstitution" xml:id="struct-413221" status="VALID">
          <idno type="IdRef">221333754</idno>
          <idno type="ROR">https://ror.org/02en5vm52</idno>
          <orgName>Sorbonne Université</orgName>
          <orgName type="acronym">SU</orgName>
          <date type="start">2018-01-01</date>
          <desc>
            <address>
              <addrLine>21 rue de l’École de médecine - 75006 Paris</addrLine>
              <country key="FR"/>
            </address>
            <ref type="url">http://www.sorbonne-universite.fr/</ref>
          </desc>
        </org>
      </listOrg>
      <listOrg type="projects">
        <org type="anrProject" xml:id="projanr-50500" status="VALID">
          <idno type="anr">ANR-19-CE25-0005</idno>
          <orgName>SAPPORO</orgName>
          <desc>Sûreté et preuve de protocoles adaptatifs pour robots oublieux</desc>
          <date type="start">2019</date>
        </org>
        <org type="anrProject" xml:id="projanr-53645" status="VALID">
          <idno type="anr">ANR-19-CE25-0003</idno>
          <orgName>Koala</orgName>
          <desc>Configurations d'environnements fog large-échelle</desc>
          <date type="start">2019</date>
        </org>
      </listOrg>
    </back>
  </text>
</TEI>