image/svg+xml NFA DFA NFA Straubing-Thérienhierarchy Complexity rporr rpoNFA = self-loop deterministic poNFA a a ptNFA = confluent rpoNFA Confluent DFA a b w w w over {a,b}* Saturated poNFA Σ* Σ* L(0) = {∅, Σ*}L(n+1/2) = finite union of languages L0a1L1...anL n where ai in Σ, Li in L(n)L(n+1) = finite Bool combinations of languages of L(n+1/2) Schwentick, Thérien, Vollmer 2001 Brzozowski and Fich 1980 Krötzsch, Masopust, Thomazo 2016 Masopust and Thomazo 2015 Héam 2002 Simon 1972; Klíma and Polák 2013 rpoNFA = self-loop deterministic poNFA a a ptNFA = confluent rpoNFA a b w w w over {a,b}* Saturated poNFA Σ* Σ* Schwentick, Thérien, Vollmer 2001 Krötzsch, Masopust, Thomazo 2016 Masopust and Thomazo 2015 Héam 2002 Straubing-Thérien hierarchy L(0) = {∅, Σ*} L(1/2) = {Σ*a1Σ*a2Σ*...anΣ* | ai in Σ}Alternation Hierarchy: Σ1shuffle ideals or upward closed languages L(1) = Bool(Σ*a1Σ*a2Σ*...anΣ*)Alternation Hierarchy: BΣ1J-trivial or piecewise testable languages L(3/2)Alternation Hierarchy: Σ2Alphabetic Pattern Constraints (Bouajjani et al.) R-trivial languages Complexity of universality: Let A be an NFA over Σ. Is L(A) = Σ*?Why universality? - lower bound for inclusion and equivalence- lower bound for k-piecewise testability Complexity PSPACE-complete even if Σ = {0,1} PSPACE-complete coNP-complete if |Σ| constant PSPACE-complete coNP-complete if |Σ| constant NL-complete if |Σ|=1 NL-complete if |Σ|=1 - Inclusion/Equivalence is PSPACE-complete for ptNFAs- k-piecewise testability is PSPACE-complete for ptNFAs- ptNFA = simplest NFAs with PSPACE-complete universality- rpoNFA languages are DRE-definable- R-trivial languages: poDFA and rpoNFA- J-trivial languages: confDFA and ptNFA Consequences DFA NFA Complexity Confluent DFA a b w w w over {a,b}* Brzozowski and Fich 1980 Simon 1972; Klíma and Polák 2013 rpoNFA = self-loop deterministic poNFA a a ptNFA = confluent rpoNFA a b w w w over {a,b}* Saturated poNFA Σ* Σ* Schwentick, Thérien, Vollmer 2001 Krötzsch, Masopust, Thomazo 2016 Masopust and Thomazo 2015 Héam 2002 PSPACE-complete even if Σ = {0,1} PSPACE-complete coNP-complete if |Σ| constant PSPACE-complete coNP-complete if |Σ| constant NL-complete if |Σ|=1 NL-complete if |Σ|=1 Straubing-Thérienhierarchy L(0) = {∅, Σ*} L(1/2) = {Σ*a1Σ*a2Σ*...anΣ* | ai in Σ}Alternation Hierarchy: Σ1shuffle ideals or upward closed languages L(1) = Bool(Σ*a1Σ*a2Σ*...anΣ*)Alternation Hierarchy: BΣ1J-trivial or piecewise testable languages L(3/2)Alternation Hierarchy: Σ2Alphabetic Pattern Constraints (Bouajjani et al.) R-trivial languages Thank You
1
  1. title
  2. poNFAs
  3. poDFAs
  4. rpoNFAs
  5. confluentDFA
  6. confluentNFA
  7. whole picture 1
  8. st
  9. Level 0-1
  10. heam
  11. level 1
  12. level 1.5
  13. whole 2
  14. whole 2
  15. complexity
  16. complexity ponfa
  17. complexity rponfa
  18. complexity ptnfa
  19. complexity sponfa
  20. complexity overview
  21. consequences
  22. done