Fakulta matematiky, fyziky
a informatiky
Univerzity Komenského v Bratislave

Algorithmic Aspects of Finding Semigroups of Partial Automorphisms of Combinatorial Structures

v sobotu 17.9.2016 od 10:30 hod. v rámci konferencie ITAT 2016, Tatranské Matliare


08. 09. 2016 10.21 hod.
Od: Róbert Jajcay

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.

This workshop is sponsored by the VEGA 1/0577/14 grant aimed at investigating the relations between Semigroup Theory and Combinatorics.

Program, Saturday 17.9.2016:  

  • 10:30-10:55 Róbert Jajcay: Inverse Semigroups of Partial Automorphisms of Graphs
  • 11:00-11:25 Oleg Gutik: On the Group of Automorphisms of the Brandt Lambda0-Extension of a Monoid With Zero
  • 11:30-11:55 Otokar Grošek: Semigroups in Cryptography
  • 12:00-12:25 Mária B. Szendrei: On Products of Inverse Semigroups  

12:30-14:00 - Lunch break 

  • 14:00-14:25 László Márki: The Theory of Morita Equivalence of Semigroups
  • 14:30-15:00 Nóra Szakács: Inverse Monoids and Immersions of 2-Complexes 

15:00-15:30 Coffee Break 

  • 15:30-15:55 Emanuele Rodaro: Decidability vs Undecidability of the Word Problem in HNN-Extensions of Inverse Semigroups
  • 16:00-16:25 Tatiana Jajcayová: The Word Problem in Free Inverse Monoids 

Organizers:
Tatiana Jajcayová, Dept. of Applied Comp. Science, Róbert Jajcay, Dept. of Algebra,
Faculty of Mathematics, Physics and Computer Science, Comenius University, Bratislava, Slovakia