wiki_research

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

bounded_problem (466B)

      1 # Bounded problem
      2 
      3 "Bounded problems" are decidable versions of potentially undecidable problems. For instance, "bounded universality" means "given k, check universality for words of length up to k"
      4 
      5 studied in [axelsson2008analyzing]
      6 
      7 - [language_inclusion_bounded]
      8 - [language_equivalence_bounded]
      9 - [language_intersection_bounded]
     10 - [language_universality_bounded]
     11 - [CFG_ambiguity_bounded]
     12 
     13 Up: [formal_language_computational_problem]
     14 
     15 Aliases: bounded problems