@inproceedings{4b42cf0b0a5f4fd4a3fd83bb7ab0c5c1,
title = "On discerning strings with finite automata",
abstract = "We study the problem of discerning strings with deterministic finite state automata (DFAs, for short). We begin with a survey on the historical and algorithmic roots of this problem. Then, we focus on the maximun number of states that are necessary to separate two strings of a given length. We survey the most important results concerning this issue and we study the problem from the point of view of some alternative models of automata. The preliminary results concerning the last issue motivate us to formulate a conjecture stating that DFAs can separate any pair of strings by using a logarithmic number of states. We give some evidence supporting our conjecture.",
author = "Abuzer Yakaryilmaz and Montoya, \{J. Andres\}",
note = "Publisher Copyright: {\textcopyright} 2015 IEEE.; 41st Latin American Computing Conference, CLEI 2015 ; Conference date: 19-10-2015 Through 23-10-2015",
year = "2015",
month = dec,
day = "16",
doi = "10.1109/CLEI.2015.7360021",
language = "English",
series = "Proceedings - 2015 41st Latin American Computing Conference, CLEI 2015",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
editor = "Alex Cuadros-Vargas and Hector Cancela and Ernesto Cuadros-Vargas",
booktitle = "Proceedings - 2015 41st Latin American Computing Conference, CLEI 2015",
address = "United States",
}