wiki_research

personal research wiki
git clone https://a3nm.net/git/wiki_research/
Log | Files | Refs

automata_generalized (532B)


      1 # Generalized automata
      2 
      3 [automata] where transitions are labeled by strings rather than letters
      4 
      5 introduced in [eilenberg1974automata]
      6 
      7 The [computational_problem] of determining the minimum number of states of a generalized [automata_nondeterministic] that recognizes a given [regular_language] is [decidable] [hashiguchi1991algorithms]
      8 
      9 notion of [automata_deterministic] for this formalism: [giammarresi1995deterministic]
     10 
     11 no notion of [minimization], but [cotumaccio2024myhill] proposes a notion to make it work
     12 
     13 Up: [automata]