J. Andres Montoya, David Casas

Universidad Nacional de Colombia. Bogota Colombia

email:

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.

@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}, }

Generated by Ernesto Cuadros-Vargas