Análisis de sistemas de máquinas de estados finitos en comunicación

Abstract

En este trabajo presentamos un modelo de cómputo formado por varias máquinas de estados finitos que se pueden comunicar entre sí a través de canales FIFO. Estudiamos cuál es su expresividad y la complejidad de resolver algunos problemas en este modelo, que yace entre lo decidible y lo indecidible por aunar la simplicidad de las máquinas de estados finitos con la complejidad que aportan comunicaciones no deterministas. Estudiamos además diversas variaciones en la definición y las implicaciones que tienen estas modificaciones sobre la expresividad y complejidad del modelo.

In this work we present a computation model in which several Finite State Machines communicate via FIFO channels. We study its expressivity and the complexity of solving some decision problems regarding this model, lying on the edge between decidability and undecidability because of bringing together the simplicity of Finite State Machines and the complexity of non-deterministic communications. We also study some variations of the main model and the changes they generate in terms of expressivity and complexity.