Subscribe to recieve announcements
 
  Home
|
Archives
|
Technical Advice  

 

   Scientific Committee:
Gilbert Baumslag ,The City College of NY
Rostislav Grigorchuk,Texas A&M
Alexei Miasnikov, Stevens Institute
Mark Sapir, Vanderbilt

 

   Organizing Committee:
Murray Elder, Univ. of Newcastle (Aus)
Bob Gilman, Stevens Institute
Alexei Miasnikov , Stevens Institute
Alex Myasnikov, Stevens Institute
Denis Serbin, Stevens Institute
Alexander Ushakov, Stevens Institute

 

   Contact Information:
Denis Serbin
email:   dserbin stevens.edu    
phone: (201) 216-5425

 

   Our sponsors:

 

 

Welcome to the First Online Seminar dedicated to Group Theory and Non-Commutative Algebra.

The seminar presents a unique opportunity for mathematicians from around the world to communicate and share their ideas on a regular basis without leaving the office or even home. Participants include faculty and students from US, Canada, Australia, Europe and Russia.

If you are a first-time participant please visit the technical advice page.

Click here to enter the meeting room


Next Presentation
   Thursday,  April 16,  noon  (New York Time)

Volker Diekert
(Universitšt Stuttgart, Germany)


"Equations in free groups and EDT0L languages"

Click here to enter the meeting room

Abstract:

Let F=F(A) be a free group and W=1 be an equation with constants in A and variables X1,...,Xm over F.
In a joint work with Laura Ciobanu and Murray Elder we showed that the set of all solutions of W is an EDT0L language. This means: there is a nondeterministic finite automaton (NFA) with the following properties.

  1. The labels of the automaton are endomorphisms over a free monoid with involution C*.
  2. We have (A ∪ A-1)* ⊆ C.
  3. There is a special symbol "#" in the alphabet C such that the set of all solutions in reduced words is exactly the set of all h(#), where h ranges through the rational set of endomorphisms R accepted by the NFA.
   Moreover, the NFA has exponential size in the input specification for W.
   As a consequence of the construction we obtain an improved complexity for deciding the existential theory for free    groups. It is in NSPACE(n log n), which we believe to be space optimal. Within the same complexity we can decide    whether or not the solution set is finite. We apply the compression technique due to Jez which provides the simplest    method for deciding the existential theory. Our results generalize to free products of free and finite groups and cope    with rational constraints.

Seminar Schedule Spring 2015
Feb   5   Svetla Vassileva (Concordia University, Canada)
"Logspace and compressed word computation in finitely generated nilpotent groups"
Abstract      PDF Slides      Watch the recording ...
 
Feb  19   Funda Gul (Stevens Institute of Technology)
"Magnus embedding and algorithmic problems in groups of the form F/Nd"
Abstract      PDF Slides      Watch the recording ...
 
Mar   5   Robert Gilman (Stevens Institute of Technology)
"Verifying Biautomaticity"
Abstract      PDF Slides      Watch the recording ...
 
Mar  26   Olga Kharlampovich (Hunter College, CUNY)
"Algorithmic questions for Γ-limit groups, where Γ is a torsion-free hyperbolic group"
Abstract      PDF Slides      Watch the recording ...
 
Apr  16   Volker Diekert (Universitšt Stuttgart, Germany)
"Equations in free groups and EDT0L languages"
Abstract      PDF Slides      Watch the recording ...
 
Apr  30   TBA
 
May  14   TBA
   

For information on the website or other questions please contact
Alex Myasnikov: amyasnik@stevens.edu
(201) 216-8598
Stevens Institute of Technology
Hoboken, NJ