| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 6875649 | Theoretical Computer Science | 2018 | 23 Pages |
Abstract
A deterministic finite automaton (DFA) separates two strings w and x if it accepts w and rejects x. The minimum number of states required for a DFA to separate w and x is denoted by sep(w,x). The present paper shows that the difference |sep(w,x)âsep(wR,xR)| is unbounded for a binary alphabet; here wR stands for the mirror image of w. This solves an open problem stated in Demaine et al. (2011) [2].
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Farzam Ebrahimnejad,