Tolerant Testing of Regular Languages in Sublinear Time
A classic problem in property testing is to test whether a binary input word 𝑤 is in regular language 𝐿. Such testers distinguish the case that 𝑤 is in 𝐿 from the case where 𝑤 is 𝜖-far from 𝐿 (𝜖-far means that at least 𝜖 fraction of the bits in 𝑤 must be modified to change 𝑤 into a word in 𝐿. Otherw...
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Published: |
Massachusetts Institute of Technology
2022
|
| Online Access: | https://hdl.handle.net/1721.1/139249 |