Semigroups, Automata and Languages

Symmetric, pseudo-symmetric, and almost-symmetric numerical semigroups

Speaker: 

Pedro García-Sánchez (Universidad de Granada)

Date: 

Wednesday, 15 February, 2012 - 14:30

Venue: 

Room M007 of the Mathematics Department, FCUP

A numerical semigroup $S$ is a submonoid of $(\mathbb N,+)$ with finite complement in $\mathbb N$. Integers not in $S$ are called gaps of $S$. The largest gap is known as the Frobenius number of $S$, $F(S)$. A gap $x$ is a hole, if $F(S)-x$ is also a gap.
...

Verification Conditions for Single-assignment Programs

Speaker: 

Jorge Sousa Pinto (Departamento de Informática, Escola de Engenharia, Universidade do Minho

Date: 

Wednesday, 30 November, 2011 (All day)

Venue: 

S2, DCC-FCUP

A mechanism for generating verification conditions (VCs) for the iteration-free fragment of an imperative language is fundamental in any deductive program verification system. In this paper we revisit symbolic execution, weakest preconditions, and bounded model checking as VC-generation...

Amalgams of inverse semigroups and reversible two-counter machines

Speaker: 

Emanuele Rodaro (CMUP)

Date: 

Wednesday, 23 November, 2011 - 14:30

Venue: 

Sala 0.04 - Dep. Matemática / FCUP

(Join work with Pedro Silva) We show that the word problem for an amalgam [S1, S2; U, ω1, ω2] of inverse semigroups may be undecidable even if we assume S1 and S2 (and therefore U) to have finite R-classes and ω1, ω2 to be computable functions, interrupting a series of...

Finite automata for Schreier graphs of virtually free groups

Speaker: 

Pedro V. Silva (FCUP / CMUP)

Date: 

Wednesday, 21 September, 2011 - 13:30

Venue: 

Sala 0.04 - Dep. Matemática / FCUP

Finite automata became over the years the standard representation of finitely generated subgroups $H$ of a free group $F_A$. The Stallings construction constitutes a simple and efficient algorithm for building an automaton $S(H)$ which can be used for solving the membership problem of $H$ in $F_A...

Idempotent generators in partition monoids

Speaker: 

James East (University of Sydney)

Date: 

Monday, 2 May, 2011 - 09:00

Venue: 

Sala 0.05 – Dep.Matemática/FCUP

Partition monoids and algebras arise in representation theory in the context of Schur-Weyl duality in symmetric groups. They are also interesting from a semigroup theoretic point of view as they contain the full transformation semigroups as well as the symmetric (and dual symmetric) inverse...

THE COST OF INVERTING A FREE GROUP AUTOMORPHISM

Speaker: 

Pedro Silva (FCUP / CMUP)

Date: 

Monday, 28 February, 2011 - 10:00

Venue: 

Sala 0.05 – Dep.Matemática/FCUP

Given a free group $F_r$ on $A = \{ a_1, \ldots, a_r\}$ and an automorphism $\varphi$ of $F_r$, we can consider the norm $||\varphi|| = |a_1\varphi| + \ldots + |a_r\varphi|$. How big can be $||\varphi^{-1}||$ relatively to $||\varphi||$? More precisely, this talk concerns the complexity of the...

A categorical invariant of flow equivalence.

Speaker: 

Alfredo Costa (FCTUC/CMUC)

Date: 

Monday, 31 January, 2011 - 14:30

Venue: 

Sala 0.04 – Dep. Matemática/FCUP

The Karoubi envelope of a semigroup is a small category which plays a distinguished role in finite semigroup theory thanks to the Delay theorem of Tilson. In this talk, an application to the classification of symbolic dynamical systems is presented: up to natural equivalence, the Karoubi envelope...

Pages

Subscribe to RSS - Semigroups, Automata and Languages