RT Generic
T1 Análisis de sistemas de máquinas de estados finitos en comunicación
T2 Analysis of Communicating Finite State Machines
A1 Hidalgo Palencia, Pablo
AB 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.
AB 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.
YR 2020
FD 2020-06
LK https://hdl.handle.net/20.500.14352/10215
UL https://hdl.handle.net/20.500.14352/10215
LA spa
NO Trabajo 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/2020
DS Docta Complutense
RD 30 abr 2024