Rodríguez Laguna, IsmaelRosa Velardo, FernandoHidalgo Palencia, Pablo2023-06-172023-06-172020-06https://hdl.handle.net/20.500.14352/10215Trabajo de fin de Grado en Doble Grado de Ingeniería Informática y Matemáticas, Facultad de Informática UCM, Departamento de Sistemas Informáticos y Computación, Curso 2019/2020En 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.spaAtribución-NoComercial 3.0 Españahttps://creativecommons.org/licenses/by-nc/3.0/es/bachelor thesisopen access004(043.3)Máquinas de estados finitosMáquinas de estados finitos en comunicaciónSistemas de mensajes perdidosRedes de PetriAutómata 110.Finite State MachinesCommunicating Finite State MachinesLossy Channel SystemsPetri netsrule 110.Informática (Informática)1203.17 Informática