CEMAT -

<!doctype html> <html> <head> <meta content="text/html; charset=utf-8" http-equiv="content-type"> <title>CEMAT - </title> <link rel="stylesheet" href="https://maxcdn.bootstrapcdn.com/bootstrap/4.0.0-beta.2/css/bootstrap.min.css" integrity="sha384-PsH8R72JQ3SOdhVi3uxftmaW6Vc51MKb0q5P2rRUpPvrszuE4W1povHYgTpBfshb" crossorigin="anonymous"> <meta name="viewport" content="width=device-width, initial-scale=1, shrink-to-fit=no"> <link rel="stylesheet" type="text/css" href="css/cemat.css" media="screen"> </head> <body> <div id="header"> <a href="main.php"><img border="0" id="logo" name="logo" alt="CEMAT - Centro de Matem锟絫ica e Aplica锟斤拷es" src="imgs/logocemat.png" width="150" height="82"></a> <div id="header-links" class="d-none d-sm-block"> <a href="https://tecnico.ulisboa.pt" target="_blank"><img border="0" src="imgs/logoist.png" width="87" height="37"></a> <a href="https://ciencias.ulisboa.pt" target="_blank"><img border="0" src="imgs/Ciencias_Logo_Azul-01.png" width="86" height="35"></a> <a href="https://www.fct.pt" target="_blank"><img border="0" src="imgs/logo_fct20anos.png" style="margin-top:-3px;" width="185" height="49"></a> </div> <div id="lang-select"> <a href="?event_type_id=17&sem_id=2418&locale=pt">pt</a> | <a href="?event_type_id=17&sem_id=2418&locale=en">en</a> </div> </div> <nav class="navbar navbar-expand-lg navbar-dark bg-dark"><button aria-expanded="false" aria-label="Toggle navigation" aria-controls="navbarSupportedContent" class="navbar-toggler" data-toggle="collapse" data-target="#navbarSupportedContent"><span class="navbar-toggler-icon"> </span></button> <div id="navbarSupportedContent" class="collapse navbar-collapse"> <ul class="navbar-nav w-100 d-flex justify-content-around">  <li class="nav-item"><a data-menu="main" href="main.php#main" class="nav-link"><span>Home</span></a></li>  <li class="nav-item dropdown"><a data-menu="area.p" href="#" aria-haspopup="true" aria-expanded="false" role="button" id="navbarDropdown1" class="nav-link dropdown-toggle" data-toggle="dropdown"><span>Research Areas</span></a> <div class="dropdown-menu rounded-0 py-0" aria-labelledby="navbarDropdown1"> <a href="area.php?section=algebra&member_id=16&project_id=7#area.p" class="dropdown-item">Algebra and Computing</a> <a href="area.php?section=applied&member_id=84&project_id=4#area.p" class="dropdown-item">Applied and Numerical Analysis</a> <a href="area.php?section=modeling&member_id=83&project_id=6#area.p" class="dropdown-item">Mathematical Modeling in Biomedicine</a> <a href="area.php?section=statistics&member_id=86&project_id=5#area.p" class="dropdown-item">Statistics and Stochastic Processes</a> </div></li>  <li class="nav-item"><a data-menu="members" href="members.php#members" class="nav-link"><span>Members</span></a></li>  <li class="nav-item"><a data-menu="documents" href="documents.php#documents" class="nav-link"><span>Publications</span></a></li>  <li class="nav-item dropdown"><a data-menu="seminar" href="#" aria-haspopup="true" aria-expanded="false" role="button" id="navbarDropdown4" class="nav-link dropdown-toggle" data-toggle="dropdown"><span>Events</span></a> <div class="dropdown-menu rounded-0 py-0" aria-labelledby="navbarDropdown4"> <a href="seminars.php?event_type_id=15#seminar" class="dropdown-item">Applied and Numerical Analysis Seminar</a> <a href="seminars.php?event_type_id=16#seminar" class="dropdown-item">Probability and Statistics Seminar</a> <a href="seminars.php?event_type_id=1#seminar" class="dropdown-item">Algebra Seminars</a> <a href="seminars.php?event_type_id=17#seminar" class="dropdown-item">CEMAT's Open Seminar</a> <a href="seminars.php?event_type_id=6#seminar" class="dropdown-item">Scientific Meetings</a> <a href="seminars.php?event_type_id=5#seminar" class="dropdown-item">Courses</a> </div></li>  <li class="nav-item"><a data-menu="projects" href="content.php?section=projects#projects" class="nav-link"><span>Projects</span></a> </li>  <li class="nav-item"><a data-menu="positions" href="content.php?section=positions#positions" class="nav-link"><span>Open Positions</span></a> </li>  <li class="nav-item"><a data-menu="contacts" href="contacts.php#contacts" class="nav-link"><span>Contacts</span></a></li> </ul> </div> </nav> <div class="container" style="min-height:600px;"> <h2><a href="#" onclick="window.history.back();">Events</a> > CEMAT's Open Seminar</h2> <div class="header-bar"></div> <form method="post" name="seminar" action="seminar.php?event_type_id=17&sem_id=2418&ccsForm=seminar%3AEdit"> <table id="structure" cellspacing="0" width="100%"> <tr> <td valign="top" width="100%"> <table class="contentTable" cellspacing="0" cellpadding="0" width="100%"> <tr> <td width="100%"> <h3>An Eilenberg-like Theorem beyond regular languages</h3> <b>25/05/2018 FCUL - 15:30 - 6.2.53 </b> <br> C茅lia Borlido (Laboratoire J. A. Dieudonn茅, CNRS, Universit茅 C么te d'Azur) <br> <br> <p><p>Finite and profinite monoids have proved to be a powerful tool in the study of regular languages. On the one hand, Eilenberg's correspondence, establishing a bijection between certain classes of regular languages (so-called varieties) and certain classes of finite monoids (so-called pseudovarieties), has been used extensively to translate between combinatorial properties of regular languages and algebraic properties of finite monoids. On the other hand, combined with Reiterman's equational theory and augmented by profinite techniques, this correspondence often leads to decidability results - a central issue in Theoretical Computer Science. However, many of the classes of languages of interest to study are not regular, and so, these tools no longer apply. In 2010, Gehrke, Grigorieff and Pin [2] proposed a unified approach to the study of regular languages, using Stone duality. In particular, they realized that profinite monoids could be seen as the extended dual spaces of Boolean algebras of regular languages equipped with a residuation structure. More generally, to a Boolean algebra of (possibly non-regular) languages closed under quotients, one can assign a Boolean space equipped with a biaction of a dense monoid (so-called BiM - Boolean space with an internal monoid). While BiMs play the role of profinite monoids in the non-regular setting, the role of finite monoids is played by typed monoids introduced in [3]. Essentially, a typed monoid is a monoid enriched with a finite Boolean algebra of its powerset. The extra structure is needed since, in general, an infinite monoid will recognize far too many languages. In this talk, after providing the necessary background on Stone duality, I will present an Eilenberg-like correspondence between varieties of (possibly non-regular) languages and pseudovarieties of typed monoids, which generalizes the classical Eilenberg's Theorem. Moreover, in the same way that profinite monoids are projective limits of finite ones, we will see that BiMs can be obtained as a projective limit of certain families of typed monoids.</p> <p>This is based on joint work with Czarnetzki, Gehrke and Krebs [1].</p> <p>References: [1] C.Borlido, S.Czarnetzki, M.Gehrke, A.Krebs. Stone duality and the substitution principle. CSL 2017: 13:1-20. [2] M.Gehrke, S.Grigorieff, J.-E. Pin. A topological approach to recognition. ICALP 2010: 151-162. [3] A.Krebs, K.-J. Lange, S.Reifferscheid. Characterizing TC^0 in terms of infinite groups. {STACS} 2005: 496-507.</p></p> </td> </tr> </table> </td> </tr> </table> </form> </div> <div id="foot"> <div class="container"> <div class="text-center"> <b>CEMAT</b> - Center for Computational and Stochastic Mathematics </div> <div id="foot-bar"></div> <div class="text-center"> <a href="http://www.ist.utl.pt/" target="_blank">Instituto Superior Têcnico</a><br> <a href="http://www.fc.ul.pt/" target="_blank">Faculdade de Ciências</a><br> <a href="http://www.ul.pt/" target="_blank">Universidade de Lisboa</a><br> </div> </div> </div> <script src="./js/jquery-3.2.1.slim.min.js" integrity="sha384-KJ3o2DKtIkvYIK3UENzmM7KCkRr/rE9/Qpg6aAZGJwFDMVNA/GpGFF93hXpG5KkN" crossorigin="anonymous"></script> <script src="https://cdnjs.cloudflare.com/ajax/libs/popper.js/1.12.3/umd/popper.min.js" integrity="sha384-vFJXuSJphROIrBnz7yo7oB41mKfc8JzQZiCq4NCceLEaO4IHwicKwpJf9c9IpFgh" crossorigin="anonymous"></script> <script src="https://maxcdn.bootstrapcdn.com/bootstrap/4.0.0-beta.2/js/bootstrap.min.js" integrity="sha384-alpBpkh1PFOepccYVYDB4do5UnbKysX5WZXm3XxPqe5iKTfUKjNkCk9SaVuEZflJ" crossorigin="anonymous"></script> <script src="./js/cemat.js"></script> </body> </html>

CINXE.COM

CEMAT -