Seminar • Algorithms and Complexity — State Complexity of Square of Star-Free LanguagesExport this event to calendar

Wednesday, June 19, 2019 — 1:30 PM EDT

Sylvie Davies, Department of Pure Mathematics
University of Waterloo

The state complexity of a regular language is the minimal number of states needed to recognize that language with a DFA. Then given a unary operation on regular languages, we may ask: if the input language is recognized by a DFA with n states, what is the worst-case state complexity of the output language, as a function of n? This worst-case value is called the state complexity of the operation. For the square operation (concatenation of a language with itself), the state complexity is known if the input is an arbitrary regular language, but not if the input is a star-free language. The state complexity of many common operations on star-free languages (union, intersection, concatenation, star, reversal) is known, but square remains elusive. We describe recent progress on this still-open problem, building on some work of Brzozowski and Szykuła on large aperiodic semigroups.

Location 
DC - William G. Davis Computer Research Centre
1304
200 University Avenue West

Waterloo, ON N2L 3G1
Canada

S M T W T F S
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
31
1
2
3
4
  1. 2020 (1)
    1. January (1)
  2. 2019 (254)
    1. December (20)
    2. November (25)
    3. October (16)
    4. September (20)
    5. August (18)
    6. July (12)
    7. June (23)
    8. May (23)
    9. April (32)
    10. March (25)
    11. February (16)
    12. January (24)
  3. 2018 (220)
    1. December (16)
    2. November (19)
    3. October (26)
    4. September (22)
    5. August (17)
    6. July (20)
    7. June (13)
    8. May (25)
    9. April (34)
    10. March (24)
    11. February (3)
    12. January (1)
  4. 2017 (36)
  5. 2016 (21)
  6. 2015 (36)
  7. 2014 (33)
  8. 2013 (23)
  9. 2012 (4)
  10. 2011 (1)
  11. 2010 (1)
  12. 2009 (1)
  13. 2008 (1)