On the real-state processing of regular operations and The Sakoda-Sipser problem
J. Andres Montoya$^{1}$, David Casas$^{1}$
$^{1}$Universidad Nacional de Colombia. Bogota Colombia
email: jamontoyaa@unal.edu.co, dfcasast@unal.edu.co

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

In this work we study some aspects of state complexity related to the very famous Sakoda-Sipser problem. We study the state-complexity of the regular operations, we survey the known facts and, by the way, we find some new and simpler proofs of some well known results. The analysis of the state of art allowed us to find a new and meaningful notion: Real-state processing. We investigate this notion, looking for a model of deterministic finite automata holding such an interesting property. We establish some preliminary results, which seem to indicate that there does not exists a model of deterministic finite automata having real-state processing of regular expressions, but, on the other hand, we are able to exhibit a deterministic model of finite automata having real-state processing of star free regular expressions.

BibTex

@InProceedings{CLEI-2015:142372,
	author 		= {J. Andres Montoya and David Casas},
	title 		= {On the real-state processing of regular operations and The Sakoda-Sipser problem},
	booktitle 	= {2015 XLI Latin American Computing Conference (CLEI), Special Edition},
	pages 		= {57--65},
	year 		= {2015},
	editor 		= {Universidad Católica San Pablo},
	address 	= {Arequipa-Peru},
	month 		= {October},
	organization 	= {CLEI},
	publisher 	= {CLEI},
	url 		= {http://clei.org/clei2015/142372},
	isbn 		= {978-9972-825-91-0},
	}