<!DOCTYPE article PUBLIC "-//NLM//DTD JATS (Z39.96) Journal Archiving and Interchange DTD v1.0 20120330//EN" "JATS-archivearticle1.dtd">
<article xmlns:xlink="http://www.w3.org/1999/xlink">
  <front>
    <journal-meta />
    <article-meta>
      <title-group>
        <article-title>Algorithmic Aspects of Finding Semigroups of Partial Automorphisms of Combinatorial Structures (AAFSPACS 2016)</article-title>
      </title-group>
      <contrib-group>
        <aff id="aff0">
          <label>0</label>
          <institution>Tatiana Jajcayová Róbert Jajcay Comenius University in Bratislava</institution>
          ,
          <country>Slovakia Workshop organizers</country>
        </aff>
      </contrib-group>
      <abstract>
        <p>The problem of the time complexity of determining the full automorphism group of a combinatorial structure (for example a graph) is one of the well-known unsettled algorithmic problems with numerous practical implications in a number of fields. The relevance of this topic was well documented by the immense interest exhibited by the research community with regard to the recent breakthrough of Laszlo Babai who announced the discovery of a quasipolynomial time algorithm for graphs. The focus of our workshop will be on an extension of the automorphism group problem to that of inverse semigroup problem. The full inverse semigroup of partial automorphisms of a combinatorial structure is a much richer algebraical structure that contains the automorphism group of the combinatorial object as a subgroup. Furthermore, the inverse semigroup of partial automorphisms contains much more detailed local information about the underlying object. Thus, the problem of determining the full inverse semigroup of partial automorphisms of a combinatorial structure is at least as hard as the corresponding automorphism group problem. In our workshop, we focus on algorithmic problems related to determining the inverse semigroup of a combinatorial structure as well as related problems of finding structures with a given inverse semigroup, and applications of inverse semigroups to constructing objects with a prescribed relation between their local and global properties. Presenters at his workshop submitted only abstracts, no full-length papers were solicited. This workshop is sponsored by the VEGA 1/0577/14 grant aimed at investigating the relations between Semigroup Theory and Combinatorics.</p>
      </abstract>
    </article-meta>
  </front>
  <body />
  <back>
    <ref-list />
  </back>
</article>