On discerning strings with finite automata
Abuzer Yakaryilmaz$^{1}$, J. Andres Montoya$^{2}$
$^{1}$National Laboratory for Scientific Computing. Petropolis Brazil,
$^{2}$Universidad Nacional de Colombia. Bogota Colombia
email: abuzer@lncc.br, jamontoyaa@unal.edu.co

Schedule:Tue 20th@15:15, Room: D

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 maximum 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.

BibTex

@InProceedings{CLEI-2015:142370,
	author 		= {Abuzer Yakaryilmaz and J. Andres Montoya},
	title 		= {On discerning strings with finite automata},
	booktitle 	= {2015 XLI Latin American Computing Conference (CLEI)},
	pages 		= {805--809},
	year 		= {2015},
	editor 		= {Hector Cancela and Alex Cuadros-Vargas and Ernesto Cuadros-Vargas},
	address 	= {Arequipa-Peru},
	month 		= {October},
	organization 	= {CLEI},
	publisher 	= {CLEI},
	url 		= {http://clei.org/clei2015/142370},
	isbn 		= {978-1-4673-9143-6},
	}