User Tools

Site Tools



This shows you the differences between two versions of the page.

Link to this comparison view

termine:ss14:140424 [22.04.2014 18:27] (current)
ctadmin created
Line 1: Line 1:
 +====== 24.04.2014 - Martin Köhler (TU Kaiserslautern) ​ ======
 +^ Time       | 11:30    |
 +^ Room       | 34-420 ​  |
 +===== Title =====
 +Recognizability of Rational Sets 
 +===== Abstract =====
 +Deterministic and non-deterministic finite
 +automata accept the same family of sets of finite
 +words, namely the regular languages. However,
 +determinism and non-determinism do not necessarily
 +coincide for other structures such as ω-words or
 +elements of certain monoids. This work will mainly
 +be concerned with monoids. This work will regard
 +rational subsets as a generalization of
 +non-deterministic finite automata and recognizable
 +subsets as a generalization of deterministic
 +finite automata. These families of subsets can be
 +regarded as deterministic and non-deterministic
 +finite automata over monoids. ​ Some basic results
 +on recognizable and rational subsets will be
 +presented in order to illustrate the difference
 +between these families of subsets. The main
 +statement of this work is the decidability of
 +recognizability of rational subsets of finitely
 +generated, commutative monoids. As an application,​
 +the result will be used to present a solution on
 +inclusion problems between rational and
 +recognizable subsets of finitely generated,
 +commutative monoids. ​
termine/ss14/140424.txt · Last modified: 22.04.2014 18:27 by ctadmin