University COVID-19 update

The University of Waterloo is constantly updating our most Frequently Asked Questions.

Questions about buildings and services? Visit the list of Modified Services.

Please note: The University of Waterloo is closed for all events until further notice.

PhD Thesis DefenceExport this event to calendar

Friday, September 27, 2019 — 11:00 AM EDT

Sylvie Davies, Department of Pure Mathematics, University of Waterloo

"Algebraic Approaches to State Complexity of Regular Operations"

The state complexity of operations on regular languages is an active area of research in theoretical computer science. We describe various algebraic techniques for attacking state complexity problems. Our central result is a general method for constructing witness languages for operations - languages which attain the worst-case state complexity when used as the argument(s) of the operation. When a witness for an operation is known, determining the state complexity becomes essentially a combinatorial counting problem. We then look at methods to simplify the solution of these counting problems by taking advantage of the connections between regular languages and finite monoids.

MC 2009

S M T W T F S
29
30
31
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
1
2
  1. 2020 (64)
    1. March (16)
    2. February (26)
    3. January (22)
  2. 2019 (199)
    1. December (7)
    2. November (26)
    3. October (19)
    4. September (13)
    5. August (7)
    6. July (12)
    7. June (18)
    8. May (22)
    9. April (11)
    10. March (25)
    11. February (17)
    12. January (22)
  3. 2018 (219)
  4. 2017 (281)
  5. 2016 (335)
  6. 2015 (209)
  7. 2014 (235)
  8. 2013 (251)
  9. 2012 (135)