On the gap between separating words and separating their reversals


          

刊名：Theoretical computer science
作者：Ebrahimnejad, Farzam（Sharif Univ Technol, Dept Comp Engn, Tehran, Iran）
刊号：738LB004
ISSN：0304-3975
出版年：2018
年卷期：2018, vol.711
页码：79-91
总页数：13
分类号：TP3
关键词：Words separation；Finite automata
参考中译：
语种：eng
文摘：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 vertical bar sep(w, x) - sep(w(R), X-R)vertical bar 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]. (C) 2017 Elsevier B.V. All rights reserved.



©2016机械工业出版社（机械工业信息研究院） 京ICP备05055788号-35