Análisis de sistemas
de Máquinas de Estados Finitos en comunicación

Analysis of Communicating Finite State Machines

Pablo Hidalgo Palencia

DOBLE GRADO EN INGENIERÍA INFORMÁTICA Y MATEMÁTICAS
FACULTAD DE INFORMÁTICA

UNIVERSIDAD COMPLUTENSE DE MADRID

Trabajo de Fin de Grado de Ingenieŕıa Informática

Curso 2019/2020

Directores:

Ismael Rodŕıguez Laguna
Fernando Rosa Velardo



i

Resumen

En este trabajo presentamos un modelo de cómputo formado por varias máqui-
nas de estados finitos que se pueden comunicar entre śı 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 im-
plicaciones que tienen estas modificaciones sobre la expresividad y complejidad del
modelo.

Palabras clave

Máquinas de estados finitos, máquinas de estados finitos en comunicación, siste-
mas de mensajes perdidos, redes de Petri, autómata 110.



ii

Abstract

In this work we present a computation model in which several Finite State Machi-
nes 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.

Keywords

Finite State Machines, Communicating Finite State Machines, Lossy Channel
Systems, Petri nets, rule 110.



Índice general

1. Introducción 1

2. Estado del arte 5

3. Definición de los sistemas con 2 máquinas 7

3.1. Sistemas donde los outputs no proliferan . . . . . . . . . . . . . . . . 10

4. Expresividad de los sistemas 12

5. Definición general de los sistemas 15

5.1. Sistemas con buffers acotados . . . . . . . . . . . . . . . . . . . . . . 17

6. Sistemas donde los outputs no proliferan 19

6.1. Ejemplo de funcionamiento . . . . . . . . . . . . . . . . . . . . . . . 19

6.2. Expresividad de los sistemas donde los outputs no proliferan . . . . 21

7. Sistemas con buffers acotados 32

8. Sistemas con buffers sin orden 35

8.1. Expresividad de los sistemas con buffers sin orden . . . . . . . . . . 36

8.2. Comparativa con otros tipos de redes de Petri . . . . . . . . . . . . . 39

9. Sistemas de Mensajes Perdidos 43

9.1. Introduciendo justicia en las ejecuciones . . . . . . . . . . . . . . . . 44

10.Complejidad de algunas propiedades 47

10.1. El problema de la alcanzabilidad finita . . . . . . . . . . . . . . . . . 47

10.1.1. En sistemas con buffers acotados . . . . . . . . . . . . . . . . 51

10.2. El problema de regreso al estado inicial . . . . . . . . . . . . . . . . 52

10.3. Otros problemas de complejidad mayor . . . . . . . . . . . . . . . . . 58

iii



ÍNDICE GENERAL iv

11.Un sistema Turing universal 61

12.Conclusiones 67



Caṕıtulo 1

Introducción

En la literatura cient́ıfica, en particular en la de la Informática, es frecuente
encontrarse situaciones en las cuales los investigadores tienen un problema que re-
solver que no se ajusta perfectamente a ningún modelo preestablecido conocido, si
bien puede ser solventado de forma sencilla creando un modelo ad hoc para la si-
tuación a partir de otros ya estudiados en profundidad. Por ejemplo, en numerosas
ocasiones, al enfrentarse a ciertos problemas, los autores deciden dividir el problema
en varias secciones sencillas e interconectarlas entre śı. Notemos que esto también
se hace en la vida real: la mayoŕıa de los trabajos complejos se suelen realizar di-
vidiéndolos en partes más pequeñas y sencillas (que podrán serán realizadas por
diferentes personas) y después juntándolas.

Este es el caso de nuestro estudio: es frecuente que al tener que modelizar pro-
tocolos concurrentes en la Informática, por ejemplo, se utilice la misma táctica que
comentábamos. En concreto, el protocolo se realiza por medio de instancias pe-
queñas más sencillas, como pueden ser las que realizan las máquinas de estados
finitos, elementos bastante sencillos y estudiados; estableciendo una comunicación
entre las distintas máquinas para que puedan simular el protocolo completo.

No obstante, estas construcciones complejas hechas a partir de máquinas de
estados sencillas se suelen hacer ad hoc para la situación en la que se esté interesado,
y esto hace que en general no se puedan reutilizar ciertos resultados ya existentes
en ejemplos similares en la literatura.

En este trabajo pretendemos hacer un estudio más general sobre estos sistemas
formados por máquinas de estados en comunicación, de forma que pueda estable-
cer unas bases para saber qué propiedades podŕıa tener un sistema concreto que
utilicemos en otros trabajos con un fin más determinado. Por ejemplo, si para una
investigación posterior usamos un modelo similar a los que vamos a explicar en este
estudio, ¿resultarán propiedades de decisión básicas como terminación o alcanzabi-
lidad decidibles o tratables? Los resultados que veremos en los siguientes caṕıtulos
ayudarán a responder este tipo de preguntas.

Además, dada la variabilidad y versatilidad de este tipo de sistemas, resultará
interesante investigar sus propiedades en función de los diferentes tipos de definición
que podamos hacer de ellos, por lo cual trataremos varios tipos de sistemas para
poder establecer comparativas entre sus propiedades, lo que creemos que podŕıa ser
de utilidad a la hora de vernos en la necesidad de usar alguno de estos sistemas.

El texto irá organizado por caṕıtulos. En el caṕıtulo 2 daremos una visión am-
plia sobre literatura relacionada con nuestro trabajo. En el caṕıtulo 3 veremos una

1



Caṕıtulo 1 - Introducción 2

definición de un modelo simplificado de los sistemas de máquinas de estados en co-
municación, que nos ayudará a comprender mejor los conceptos antes de entrar en
el caso general. En el caṕıtulo 4 veremos que esta simplificación de los sistemas es
un modelo Turing completo. Con esto, en el caṕıtulo 5 llegamos ya a la definición de
los sistemas generales que trataremos a partir de ah́ı. En el caṕıtulo 6 estudiaremos
más a fondo el caso de los sistemas donde los outputs no proliferan, que resultan ser,
como reconocedores de lenguajes, un modelo completo dentro del de los dependien-
tes del contexto. En el siguiente caṕıtulo, el 7, explicamos que los sistemas donde
los buffers están acotados no pueden reconocer más allá de los lenguajes regulares.
En el caṕıtulo 8 estudiamos qué ocurre en el caso de que se pierda el orden de los
mensajes intercambiados en nuestros sistemas, ya que obtenemos modelos compara-
bles a diferentes tipos de redes de Petri, los modelos más representativos cuando no
hay orden en los sistemas. Más tarde, en el caṕıtulo 9, estudiamos qué ocurre cuan-
do otra propiedad básica de los sistemas cambia, concretamente qué ocurre cuando
los canales de comunicación pueden fallar, y su relación con los conocidos Sistemas
de Mensajes Perdidos. Tras todo esto, llegamos al caṕıtulo 10, donde estudiamos
la complejidad de resolver diferentes problemas de decisión sobre las cualidades de
nuestros sistemas, centrándonos en el problema de la alcanzabilidad finita y de re-
greso al estado inicial. Por último, presentamos en el caṕıtulo 11 un sistema bastante
sencillo que es Turing universal, por medio de una simulación del autómata 110.



Introduction

As we can see in the existing scientific literature, it is quite usual that a researcher
faces a problem which does not fit exactly in an existing model, but can be easily
solved creating an ad hoc model for this situation based on others which have been
studied in depth. For instance we can find the situation where a researcher splits
a problem into smaller and simpler sections and then connects all them properly.
Notice that this is not a unique feature from research, we do this in our daily life: we
carry out the vast majority of the difficult works using a strategy that first divides
the whole task into smaller subtasks (which are commonly done by different people)
and then join everything.

This will be our case: for instance it is common that the strategy explained above
is used when modelling concurrent protocols in Computer Science. More concretely,
the protocol is carried out by means of smaller systems, such as Finite State Ma-
chines -which are really simple and have been studied broadly- which can join their
efforts if we establish some kind of communication among them.

Although this is a common situation, these complex constructions are often in
practice really ad hoc, in the sense that they are not directly reusable in other
situations than the one they were thought for. This makes it more difficult to reuse
not only the definitions, but also the results and properties that were proved for
those models.

In this work we aim to study in a broad generality this kind of systems where
some Finite State Machines can communicate among them, with the purpose of
establishing some foundation in the topic which can be later used to know which
kind of properties are to expect from a concrete similar model that anyone could
need in a research. If it were the case that we used a similar model in another work,
would some basic properties of that model such as termination or reachability be
decidable or tractable? The results we are about to develop in the next chapters will
help to answer this sort of questions.

Furthermore, given the variability and flexibility of this kind of systems, it will
be of great interest to investigate their properties in terms of the different definitions
we can use, in order to state a comparative among some of the possible models that
can be created from the same abstraction. This can turn out to be really useful
when deciding which model best fits a concrete situation we are interested in.

The text will be divided into chapters. In Chapter 2 we will take a look at the
existing literature related to our work. In Chapter 3 we will introduce the topic by
studying a simplified version of our final model, which only comprises a maximum
of two Finite State Machines, and will help us understand better the key concepts.
In Chapter 4 we prove that this simplified model is Turing complete. In Chapter 5
we arrive to the definition of the main model we are interested in. In Chapter 6 we

3



Caṕıtulo 1 - Introducción 4

study a submodel where the amount of information used to communicate is limited
(the Finite State Machines can communicate with only one machine at a time),
which results to be complete among the context-sensitive language recognizers. We
study next, in Chapter 7, the case where the size of the buffers used to communicate
is bounded, which results in a model that can only recognize regular languages. In
our path studying variations of the main model we get to the Chapter 8, where the
order of the messages exchanged between machines is in some sense lost, and the
resulting model is comparable to different kinds of Petri nets. In Chapter 9 we study
the case where another crucial property of the communications is changed: if the
channels used for communications are faulty, the formalism becomes really similar
to Lossy Channel Systems, and we will study the connections more in detail. All this
been studied we arrive to Chapter 10, where we look into some decision problems on
our models and their complexity, focusing on some finitary versions of reachability
and home-state problems. Finally in Chapter 11 we present a really simple system
which is (Turing-)universal, based on Rule 110.



Caṕıtulo 2

Estado del arte

Como dećıamos, en la literatura ya hay numerosos ejemplos de situaciones en las
cuales una agrupación de máquinas de estados finitos (de diferentes tipos) se pueden
comunicar a través de una serie de canales (con diferentes propiedades). Esto en
general se debe a que, al estar constituidas por máquinas de estados finitos, son
fáciles de programar y entender su funcionamiento, a la par que son muy versátiles
(podemos añadir propiedades a las máquinas o a los canales dependiendo de nuestra
situación) y pueden llegar a tener una expresividad muy grande.

Por esta versatilidad de la que hablamos, en general no suele haber una definición
que concuerde en todos los casos. En numerosas ocasiones la definición de estos
sistemas de máquinas de estados en comunicación coincide con el que usaremos
nosotros en el caso general: canales FIFO ideales y máquinas de estados finitos
deterministas. Ejemplos de art́ıculos que usen esta definición son numerosos: [7, 10,
13, 15, 16, 23, 25].

No obstante, hay algunos casos en los que difieren algunos detalles. Por ejemplo,
en [7], que fue uno de los primeros art́ıculos que introdujo este tipo de sistemas
ya en 1983, la comunicación entre n máquinas se produce con n2 canales: cada
máquina tiene un canal de comunicación directo con cualquier otra máquina, de
forma que no se mezclan los mensajes. En otros casos, como [13, 23] se restringen al
estudio de únicamente 2 máquinas, que ya veremos más adelante (caṕıtulo 4) que
es suficientemente interesante. Hay también situaciones en los que se introducen
capacidades especiales a las máquinas, como las de hacer test de vaćıo de los canales
que leen, como en [25] (veremos una situación similar en el apartado 8.2).

Como hemos explicado, nuestro objetivo es inferir propiedades de este tipo de
sistemas de forma teórica. Sobre todo porque este tipo de trabajo no se ha hecho en
profundidad con estos sistemas: muchos autores utilizan estas construcciones para
modelizar distintos protocolos de comunicación por la versatilidad de las comuni-
caciones (en art́ıculos similares a [6, 7, 10, 23]). Pero no muchos art́ıculos versan
sobre averiguar las propiedades generales de estos sistemas. Quizá en esta dirección
podŕıamos citar [13, 15, 16, 23, 25], pero en su mayoŕıa no investigan sistemas gene-
rales, sino únicamente subclases que les interesan para sus propósitos determinados.
En general, la propiedad más estudiada es la acotación de los canales a lo largo de
las ejecuciones de los sistemas, por lo que en nuestro caso no la vamos a tratar tanto.

También es amplio el espectro de ejemplos en los cuales los canales no son de
tipo FIFO e ideales. Por ejemplo, hay una gran teoŕıa desarrollada sobre Sistemas
de Mensajes Perdidos, en los cuales los canales pueden perder mensajes de manera

5



Caṕıtulo 2 - Estado del arte 6

no determinista. Ejemplos de art́ıculos que los analizan son [2, 26], cuyos autores
han escrito bastantes más art́ıculos sobre este tema. Nosotros los trataremos en el
caṕıtulo 9 por ser uno de los sistemas más importantes que se pueden modelizar con
máquinas de estados en comunicación.

También hay ocasiones en los que hay ciertas nociones de prioridad entre los ca-
nales, como en [14]. O incluso situaciones que llegan a un nivel mayor de abstracción
y subsumen a varias de las que hemos comentado, como en el caso de [5, 6].

Viendo la literatura existente, de la que hemos intentado resumir aqúı sus prin-
cipales vertientes (aunque cada una de ellas es mucho más amplia), concluimos que
los sistemas de máquinas de estados en comunicación son ampliamente utilizados
con diferentes propósitos y definiciones, pero no se han estudiado sus propiedades
salvo en casos concretos que vinieran bien para un trabajo. Por tanto, vemos conve-
niente intentar al menos hacer un estudio de varias de las propiedades de este tipo
de sistemas en su versión más usual. Y al haber muchas variaciones en la defini-
ción de los sistemas, exploraremos cómo van variando estas propiedades al variar
las definiciones.



Caṕıtulo 3

Definición de los sistemas con 2
máquinas

Antes de ir al caso general de nuestro estudio, vamos a estudiar un subcaso
sencillo que tiene interés por śı mismo, y que allanará el camino para entender
mejor los siguientes razonamientos. En este apartado limitaremos nuestros sistemas
a tener únicamente dos máquinas de estados, con lo que será más fácil comprender
su funcionamiento.

Supongamos que tenemos F1, F2 dos máquinas de estados finitos (FSM por sus
siglas en inglés), de tipo Mealy: F1 = (Q1, I1, O1, q

0
1, δ1), F2 = (Q2, I2, O2, q

0
2, δ2),

donde Qi es el conjunto (finito) de estados de la máquina Fi, Ii el alfabeto de sus
inputs, Oi el alfabeto de sus outputs, q0

i ∈ Qi es su estado inicial y δi : Qi × I?
i −→

Qi×O?
i es una función parcial, llamada función de transición, siendo X? := X∪{ε}.

δi(q, α) = (q′, β) significa que si la máquina Fi está en el estado q y le llega el input
α 6= ε, puede transitar hacia el estado q′ produciendo el output β. Y si α = ε,
significa que dicha transición se puede tomar sin que llegue ningún literal, como es
habitual. Notemos que al ser δi una función parcial, no tiene por qué estar definida
para todos los posibles pares (q, α) ∈ Qi × I?

i : habrá valores que tengan imagen,
pero no necesariamente todos.

Gráficamente representaremos los diferentes estados de una FSM con ćırculos,
y las transiciones mediante flechas: si una flecha va de q a q′ y tiene la anotación
X/Y , estará representando la transición δ(q,X) = (q′, Y ).

Es importante darse cuenta de que las máquinas F1, F2 pueden efectuar transi-
ciones sin necesidad de consumir literales de su input, pues ε ∈ I?

i . Esto significa
que pueden generar más outputs que inputs reciben, fenómeno al cual llamaremos
proliferación de outputs. Notemos que esta forma de que los outputs proliferen es
equivalente a otras, como por ejemplo la que se generaŕıa si δi : Qi× Ii −→ Qi×O∗i .
Esta equivalencia se puede ver de la siguiente forma: si tenemos una función de
transición del tipo δ : Q×I −→ Q×O∗, simplemente podemos crear nuevos estados
allá donde se produzca más de un output (si se producen n outputs, generamos n−1
estados auxiliares), como sugiere la figura 3.1, y que más adelante formalizaremos
más en detalle. En el otro sentido, tendŕıamos que eliminar estos estados auxiliares,
en los cuales se generan outputs sin consumir inputs, es decir, que tiene transiciones
consumiendo ε. Esto se puede hacer siguiendo un procedimiento similar al conocido
método que nos permite reducir autómatas finitos no deterministas con transiciones
ε a autómatas finitos no deterministas (sin transiciones ε), tomando las denominadas
ε-clausuras.

7



Caṕıtulo 3 - Definición de los sistemas con 2 máquinas 8

q1 q′1
A/BC

q1 qaux q′1
A/B ε/C

Figura 3.1: Ejemplo de transformación de una transición en la que se pueden pro-
ducir varios outputs en otra en la cual solo se permite producir un output en cada
transición.

Como vamos a establecer sistemas para que las máquinas se comuniquen, note-
mos que los alfabetos con los que se comunican F1, F2 tienen que ser coherentes entre
śı. En concreto, para que la máquina F1 comprenda los literales que F2 le manda,
se debe cumplir O2 ⊆ I1. Por simplicidad podemos suponer en realidad O2 = I1 sin
más que pensar que F2 no tiene por qué generar outputs de todos los literales de su
alfabeto, como es natural. Análogamente, podemos suponer O1 = I2. Además, por
simplicidad también asumiremos en ocasiones que estos 4 alfabetos están dentro de
otro más grande que denotaremos Σ, que vistas las anteriores relaciones, podemos
definir simplemente como Σ := I1 ∪ I2, y sirve para hacer razonamientos con las
máquinas F1, F2 tan bien como I1, I2, O1, O2.

F1

Buffer 1

F2

Buffer 2

Figura 3.2: Visualización de la
forma en que las 2 máquinas se
comunican.

Para que realmente exista comunicación en-
tre las máquinas F1 y F2 debemos disponer de
un medio. En este caso tendremos dos buffers
B1, B2, siendo B1 el buffer en el cual escribe la
máquina F2 y lee F1, y B2 el análogo en el senti-
do contrario, como se puede ver en la figura 3.2.
Viendo estos buffers como estructura de datos,
son colas de elementos de nuestro alfabeto Σ:
B1 será una cola en la cual F2 inserta elementos
por un lado, mientras que F1 los retira desde el
otro lado. Numeraremos las posiciones del buf-
fer empezando en 0 (el extremo cercano a F1),
y crecientes a medida que nos acercamos al ex-
tremo por el que F2 inserta. De manera análoga
podŕıamos definir B2, intercambiando los pape-
les de F1 y F2.

Ahora nos damos cuenta de que el conjunto de configuraciones de un buffer
posibles es simplemente Σ∗, el conjunto de sucesiones finitas de letras de nuestro
alfabeto. Asimismo, definimos la operación + como la concatenación de elementos
de Σ∗. De esta forma, si en un buffer cuyo contenido es α encolamos la palabra β,
su contenido final lo denotaremos simplemente α+ β.

En estas condiciones, podemos pasar a definir realmente los sistemas que vamos
a utilizar:

Definición 3.1. Dadas dos FSMs F1, F2, decimos que S = (F1, F2) es un sistema
de dos máquinas de estados en comunicación asociado a F1, F2. Las configu-
raciones de S son tuplas de la forma (q1, B1, q2, B2) ∈ Q1×Σ∗×Q2×Σ∗. La función
de transición de S es δ : Q1 ×Σ∗ ×Q2 ×Σ∗ −→ Q1 ×Σ∗ ×Q2 ×Σ∗, construida de
la siguiente forma:



Caṕıtulo 3 - Definición de los sistemas con 2 máquinas 9

1. B1 = X +B′1 ∧ δ1(q1, X) = (q′1, α) =⇒ (q′1, B
′
1, q2, B2 + α) ∈ δ(q1, B1, q2, B2)

2. B2 = Y +B′2 ∧ δ2(q2, Y ) = (q′2, β) =⇒ (q1, B1 + β, q′2, B
′
2) ∈ δ(q1, B1, q2, B2)

Primero notar que las configuraciones (q1, B1, q2, B2) se pueden interpretar como
si estuviéramos indicando el estado de cada FSM mediante q1 y q2 y los conteni-
dos de los buffers que en los párrafos anteriores comentábamos fueran B1 y B2,
respectivamente.

Las transiciones expuestas en la definición simplemente significan que, en cada
configuración (q1, B1, q2, B2) de S, se puede avanzar de dos maneras: dando F1 un
paso según su definición, o dándolo F2. En este sentido, si es la máquina F1 la que
avanza, ha de usar el primer literal de su buffer, digamos X (y B′1 es el resto del
buffer), para saber qué transición toma, siendo esta δ1(q1, X). Si esta entrada de
la función δ1 está definida, es decir, δ1(q1, X) = (q′1, α) para ciertos q′1 ∈ Q1, α ∈
Σ?, entonces se podrá encolar α en B2 para llegar a la nueva configuración de S:
(q′1, B

′
1, q2, B2 + α). De manera análoga podemos razonar qué sucede en S si es F2

quien avanza un paso.

Teniendo estas transiciones en nues-
tras FSMs:

En F1:

q1 q′1
X/α

En F2:

q2 q′2
Y/β

Obtendŕıamos un comportamiento si-
milar al siguiente:

(q1, B1,
q2, B2)

(q′1, B
′
1,

q2, B2 + α)

(q1, B1 + β,
q′2, B

′
2)

un paso de F1

un paso de F2

Figura 3.3: Representación de las diferentes transiciones de S en función de las tran-
siciones que pueden tomar F1 y F2 estando en los estados q1 y q2, respectivamente,
y siendo los contenidos de los buffers B1 = X+B′1 y B2 = Y +B′2, respectivamente.

Los sistemas de máquinas de estados en comunicación aśı construidos son inhe-
rentemente no deterministas, a pesar de que las máquinas de que están compuestos
pudieran ser deterministas: hay configuraciones del sistema S en las cuales podŕıan
avanzar un paso tanto la máquina F1 como la máquina F2 (cuando el primer literal
del contenido sus buffers no bloquea su avance). Aśı, el sistema puede avanzar en
diferentes direcciones en una misma situación, lo cual resulta en un comportamiento
no determinista. Básicamente esto se produce porque las comunicaciones entre F1

y F2 dentro de S se producen de forma aśıncrona: no hay ningún mecanismo que
regule quién puede mandar información a la otra máquina, y esto genera que ambas



Caṕıtulo 3 - Definición de los sistemas con 2 máquinas 10

máquinas puedan avanzar pasos en su ejecución de forma casi independiente, lo cual
da mucha libertad al sistema S.

Además, en este tipo de sistemas existe también el concepto de configuración
de aceptación. Consideraremos que S tiene un conjunto de estados finales QF ⊆
Q1 ∪ Q2, y que una configuración (q1, B1, q2, B2) será de aceptación si q1 ∈ QF o
q2 ∈ QF . Es decir, los sistemas de FSMs en comunicación aceptan cuando una de sus
máquinas acepta, independientemente de cuáles sean los contenidos de los buffers.

Como es habitual, gráficamente los distintos estados de aceptación de las FSMs
los representaremos con ćırculos dobles, para diferenciarlos de los ćırculos simples
que representan el resto de estados.

Naturalmente habŕıa más maneras de definir el concepto de aceptación en este
tipo de sistemas, como aceptar por buffers vaćıos, con unos ciertos contenidos de
los buffers, generando literales especiales, cuando cada máquina estuviera en un
estado de aceptación... No obstante, consideramos que la forma que hemos definido
y usaremos es bastante útil y versátil en la práctica. De hecho, incluso podŕıa servir
para simular otras de las formas que acabamos de comentar.

De esta forma, los sistemas de FSMs en comunicación tienen una forma de re-
conocer lenguajes: diremos que un sistema S = (F1, F2) acepta una palabra ω ∈ Σ∗

si puede llegar a una configuración de aceptación desde la configuración inicial
(q0

1, ω, q
0
2, ε), es decir, la configuración de S en la cual cada FSM está en su estado

inicial y la palabra a evaluar está ı́ntegramente en el buffer de la primera máquina
(sin pérdida de generalidad, pues podŕıamos haberlas renombrado). Notemos que
esta forma de aceptar se parece bastante a la de las máquinas de Turing usuales,
pues en ellas también la configuración inicial parte de tener la palabra por completo
en la cinta, con el cabezal apuntando a su principio.

3.1. Sistemas donde los outputs no proliferan

Como comentábamos al inicio, en este estudio pretendemos hacer comparativas
entre diferentes tipos de definiciones de los sistemas. En este sentido, vamos a definir
un primer subtipo de nuestros sistemas generales.

Como hemos visto en las páginas anteriores, gran parte del potencial de los
sistemas de FSMs en comunicación parece provenir del fenómeno de proliferación de
los outputs. Para confirmar esta intuición, posteriormente haremos una comparativa
con el comportamiento de sistemas en los cuales los outputs no proliferan. Para ello,
pasamos a definirlos brevemente.

Definición 3.2. Decimos que S = (F1, F2) es un sistema de FSMs en comu-
nicación en el cual los outputs no proliferan si se cumple que las funciones
de transición de las máquinas F1 y F2 no dejan proliferar los outputs, es decir, si
δ1 : Q1 × I1 −→ Q1 ×O?

1 y δ2 : Q2 × I2 −→ Q2 ×O?
2.

De esta forma, en el sistema S la cantidad de literales que hay en B1 y B2 va
a permanecer controlada en cada momento: como tanto F1 como F2 solo producen



Caṕıtulo 3 - Definición de los sistemas con 2 máquinas 11

como mucho tantos outputs como inputs consumen, deducimos que la cantidad
de literales en S, es decir, |B1| + |B2| nunca puede crecer a lo largo de cualquier
ejecución.



Caṕıtulo 4

Expresividad de los sistemas

Una vez claras las definiciones, vamos a estudiar primeramente cuál es la expre-
sividad de los sistemas que acabamos de definir. Va a resultar interesante comprobar
que, a pesar de la simplicidad de las definiciones, los sistemas de FSMs en comuni-
cación son Turing completos. Para la demostración de este hecho nos basaremos en
una comparativa con los autómatas con cola, que presentamos aqúı brevemente.

Definición 4.1. Un autómata con cola M es una tupla M = (Q,Σ,Γ, $, q0, δ),
donde Q es un conjunto (finito) de estados, Σ ⊂ Γ es el alfabeto usado por los inputs,
Γ es el alfabeto que usa la cola, $ ∈ Γ \ Σ es el śımbolo inicial de la cola, q0 ∈ Q es
el estado inicial de M y δ : Q× Γ→ Q× Γ∗ es la función de transición.

La función de transición actúa de forma similar al caso de los autómatas con pila,
que también utilizan cierta memoria adicional, pero en esta ocasión utilizando una
estrategia LIFO: las transiciones toman un literal del principio de la cola y devuelven
varios literales que se meten por el final de la cola. Cabe mencionar también que los
autómatas con cola aceptan por cola vaćıa.

Lo más interesante para nosotros en este momento es que los autómatas con co-
la forman un sistema Turing completo, pues pueden simular cualquier máquina de
Turing, y de hecho en tiempo polinómico (como se puede consultar en [19], ejercicio
99, por ejemplo). De esto resulta que una demostración sencilla de la Turing com-
pletitud de los sistemas de FSMs en comunicación se base en reducir un autómata
con cola a uno de estos sistemas. Además, aunque no hace falta para probar la
Turing completitud, esta reducción se puede hacer polinómica, lo cual será de utili-
dad posterior para demostrar otras propiedades. En el siguiente resultado vamos a
desarrollar esta idea en profundidad.

Teorema 4.2. El conjunto de sistemas de FSMs en comunicación en los cuales los
outputs proliferan (según la definición 3.1) es Turing completo.

Demostración. Sea M = (Q,Σ,Γ, $, q0, δ) un autómata con cola, según la de-
finición anterior 4.1. Entonces podemos crear un sistema S = (F1, F2), con buffers
B1, B2, de dos máquinas en comunicación que simulen el comportamiento de M de
forma que F1 simule las transiciones de M (a través de la función de transición
δ1), mientras que F2 simplemente haga que todos los inputs que le llegan desde B2

acaben en B1 (a través de δ2). De esta forma, al ser los buffers colas, se comportarán
como la cola de nuestro autómata M.

No obstante, hemos de poner atención a la hora de definir F1, pues la forma que
tiene M de hacer que los outputs proliferen es generando varios literales con una

12



Caṕıtulo 4 - Expresividad de los sistemas 13

misma transición (recordemos δ : Q×Γ→ Q×Γ∗), mientras que F1 lo hace un tanto
diferente, a través de su función de transición δ1 : Qi×Σ? −→ Q1×Σ?. En el primer
caṕıtulo ya vimos la intuición de que realmente estas dos formas de hacer proliferar
los outputs eran equivalentes, y aqúı vamos a ver la construcción que necesitamos
más en detalle.

Para cada estado qi ∈ Q, F1 tendrá asimismo un estado q1
i ∈ Q1. Veamos ahora

qué construcción hacemos para simular una transición arbitraria δ(qi, X) = (qj , α)
deM. Si el tamaño de α es n ∈ N, podemos decir que α = Y1 +Y2 + . . .+Yn, donde
Yk ∈ Σ son literales de nuestro alfabeto. En el caso de que n < 2 podemos simular
fácilmente la transición de δ incluyendo δ1(q1

i , X) = (q1
j , α). Y en el caso de que n ≥

2, simplemente tenemos que añadir n−1 estados auxiliares q1
i,X,1, q

1
i,X,2, · · · , q1

i,X,n−1,

junto con las transiciones δ1

(
q1
i , X

)
=

(
q1
i,X,1, Y1

)
,δ1

(
q1
i,X,1, ε

)
=

(
q1
i,X,2, Y2

)
, . . .,

δ1

(
q1
i,X,n−2, ε

)
=

(
q1
i,X,n−1, Yn−1

)
. La construcción la podemos ver gráficamente

como en la siguiente figura:

qi qj
X/α

se convierte en:

q1
i q1

i,X,1 q1
i,X,2 q1

i,X,n−1 q1
j

X/Y1 ε/Y2 · · · ε/Yn

Figura 4.1: Visualización de la transformación para que las FSMs solo produzcan
un output con cada transición.

Tenemos que tener en cuenta ahora que hay que simular la aceptación deM, que
como dijimos es por cola vaćıa. Al igual que se hace usualmente con los autómatas
con pila, en los cuales se introduce un śımbolo especial que denota el fin de la
pila, aqúı introduciremos el śımbolo # con el mismo fin. Lo primero que hará F1

será generar dicho literal desde su estado inicial q1
#, que tendrá una única transición:

δ1(q1
#, ε) = (q1

0,#), donde q1
0 es el estado asociado al estado inicial q0 deM. A partir

de ah́ı, F1 no tendrá en cuenta el literal #, pues no influye en la simulación de M.
Por ello, cada estado q ∈ Q1 obviará las # mediante la transición δ1(q,#) = (q,#).

Visto esto, la máquina F2 seŕıa realmente simple, como explicábamos en la dis-
cusión anterior: podŕıa simplemente contar con un estado q2

0 (que seŕıa el estado
inicial de F2), y con las transiciones δ2(q2

0, A) = (q2
0, A) para todos los A ∈ Γ, de

forma que lo único que hace es devolver lo que lee. Y tiene que tener también un
mecanismo de detectar la aceptación. Como tenemos que simular la aceptación de
M, que es por cola vaćıa, S debeŕıa aceptar cuando sus buffers están vaćıos. Pero
para ello hemos introducido el śımbolo #: cuando S llegue a simular a M con la
cola vaćıa, el único śımbolo que habrá en los buffers B1, B2 seŕıa #. Por tanto, F2



Caṕıtulo 4 - Expresividad de los sistemas 14

puede aceptar en cuanto vea # dos veces seguidas. Una representación gráfica se
puede ver en la figura 4.2.

q2
0 q2

# q2
f

#/#

A/A (A 6= #)

#/ε

A/A (A 6= #)

Figura 4.2: La FSM F2 de nuestro sistema.

De esta forma, el sistema que conforman F1, F2 simula el autómataM, usando el
alfabeto Γ∪{#}, con estados iniciales (q1

#, q
2
0) ∈ Q1×Q2 y estado final q2

f ∈ Q2.

Notemos además que por cada output que generaM, para simular dicha produc-
ción de un output nuestro sistema S produce únicamente 2 outputs (uno F1 y otro
F2) Esto quiere decir que los tiempos de ejecución de M y S se relacionan también
con únicamente ese factor constante 2. Por tanto, la simulación se hace en tiempo
polinómico respecto a lo que tarda M (por cada paso de M, S da una cantidad
O(1) de pasos). En cuanto a espacio también tenemos una transformación polinómi-
ca, lo cual podemos ver en la cantidad de estados de F1 y F2. Y como la reducción
de máquinas de Turing a autómatas con cola se puede hacer también con única-
mente un aumento polinómico de tiempo y espacio, concluimos que la reducción de
máquinas de Turing a sistemas de FSMs en comunicación es polinómica.



Caṕıtulo 5

Definición general de los
sistemas

Visto ya el interés que tienen los sistemas de FSMs en comunicación a través de
su gran expresividad a pesar de su aparente sencillez, como acabamos de comprobar
al ver que conforman un sistema Turing completo, pasamos a estudiar una generali-
zación natural de los sistemas que hab́ıamos considerado hasta ahora, introduciendo
un mayor número de FSMs.

Sean Fi = (Qi, Ii, Oi, q
0
i , δi), con 1 ≤ i ≤ n, un conjunto de n FSMs. De-

finimos S = (F1, F2, . . . , Fn) como el sistema de FSMs en comunicación asocia-
do a F1, . . . , Fn. Estas máquinas se comunican entre śı a través de ciertos buffers
B1, B2, . . . , Bn, de forma que Fi consume literales de Bi (desde uno de los extremos
del buffer), mientras que cualquier máquina puede escribir literales en Bi (por el
extremo contrario al que Fi lee). La configuración de S dependerá en cada instante
del estado en que está cada máquina Fi y del contenido de cada buffer Bi.

Cabe destacar que en este caso vamos a interpretar los outputs de cada máquina
Fi de una manera que nos va a resultar más cómoda. Podemos suponer que cada
función de transición ha cambiado su rango: δi : Qi × I?

i −→ Qi ×
(
O?
i

)n
(donde

Qi ×
(
O?
i

)n ⊆ Qi × I?
1 × I?

2 × · · · × I?
n para que la comunicación tenga sentido), ya

que ahora cada transición de Fi va a generar (potencialmente) un output para cada
una de las máquinas de S. Notamos además que, al igual que en el caso más sencillo
en el cual solo teńıamos 2 máquinas, los correspondientes alfabetos de las máquinas
tienen que ser coherentes entre śı para que se pueda establecer una comunicación
entre ellas. En una situación general, debeŕıamos tener Oi ⊆ Ij para cada par
1 ≤ i, j ≤ n, de forma que Fj entiende los literales que le manda Fi. En los casos
donde no sea necesario (y de hecho, resulte engorroso) lidiar con esta suerte de
detalles, denotaremos Σ := I1 ∪ I2 ∪ · · · ∪ In ∪ O1 ∪ O2 ∪ · · · ∪ On como el alfabeto
de todas las máquinas de S por simplicidad, ya que generaliza al resto de alfabetos.

La función de transición global entre las distintas transiciones de S toma ahora
la forma δ : Q1×Σ∗×Q2×Σ∗×· · ·×Qn×Σ∗ −→ Q1×Σ∗×Q2×Σ∗×· · ·×Qn×Σ∗

entre las diferentes configuraciones de S que nos ayuda a saber cómo evoluciona este
sistema. Esencialmente, simula ejecuciones de cada máquina por separado, igual que
en el caso de únicamente dos máquinas, de forma que en cada transición de S hay
una máquina Fi que da un paso en su ejecución: lee de su buffer Bi, avanza en la
dirección que le indique ese literal léıdo y env́ıa al resto de máquinas los literales
que la transición le indique, dejándolos en sus respectivos buffers. Vista la intuición,
escribámoslo de manera más precisa.

15



Caṕıtulo 5 - Definición general de los sistemas 16

Definición 5.1. Sea un conjunto de n FSMs, F1, F2, . . . , Fn, donde cada máquina es
Fi = (Qi, Ii, Oi, q

0
i , δi), con función de transición δi : Qi×Σ? −→ Qi×

(
Σ?

)n
, como

antes hemos descrito. Definimos entonces el sistema de FSMs en comunicación
asociado a estas máquinas como S = (F1, F2, . . . , Fn). Una configuración de S es
una tupla de Q1 × Σ∗ ×Q2 × Σ∗ × · · · ×Qn × Σ∗.

Además, la función de transición de S, δ, tiene transiciones que simulan pasos
de las distintas FSMs Fi, con 1 ≤ i ≤ n, pues está definida de la siguiente forma:

Bi = X +B′i ∧ δi(qi, X) = (q′i, α1, α2, . . . , αn) =⇒
(q1, B1 + α1, . . . , qi−1, Bi−1 + αi−1, q

′
i, B

′
i + αi, qi+1, Bi+1 + αi+1, . . . , qn, Bn + αn)

∈ δ(q1, B1, . . . , qi, Bi, . . . , qn, Bn)

De nuevo, una configuración (q1, B1, . . . , qn, Bn) de S se puede entender como el
conjunto de estados q1, . . . , qn en que están las distintas FSMs y el contenido de los
buffers B1, . . . , Bn en ese determinado instante. Desde una de sus configuraciones,
el sistema puede transitar a otras configuraciones con literales distintos de ε (como
mucho habrá n de este tipo), aquellas que resultan de avanzar un paso en la ejecu-
ción de cada una de las máquinas que no tengan su buffer de lectura vaćıo (y que
su función de transición les permita avanzar), y de modificar los buffers adecuada-
mente con respecto a lo que dicta esta transición. Pero también hay otro tipo de
transiciones: las asociadas a pasos en los cuales cada FSM consume ε de su buffer
correspondiente, es decir, avanza sin consumir ningún literal.

Además, recuperamos el concepto de configuración de aceptación que ya teńıamos
en el caso de sistemas con únicamente 2 máquinas: nuestro sistema S tiene un con-
junto de estados finales QF ⊆ Q1 ∪ Q2 ∪ . . . ∪ Qn de forma que una configuración
(q1, B1, q2, B2, . . . , qn, Bn) es de aceptación qi ∈ QF para algún ı́ndice i ∈ {1, . . . , n}.

De igual manera, la forma en que estos sistemas reconocen palabras es la misma
que la que usaban sus análogos con únicamente dos máquinas y que explicamos
en 3: consideraremos que un sistema acepta una palabra si una configuración de
aceptación es alcanzable tras comenzar en la configuración inicial que surge de tener
a cada FSM en su estado inicial y todos los buffers vaćıos, excepto el de la (sin
pérdida de generalidad) primera máquina, que contiene dicha palabra.

En estos sistemas el fenómeno de proliferación de los outputs es todav́ıa más
claro: además de lo que ocurŕıa en el caso con únicamente dos máquinas, que aqúı
también se da (pues seguimos pudiendo generar outputs sin consumir inputs), por
cada transición de una máquina se está consumiendo un literal (a lo sumo), mientras
que potencialmente se podŕıan generar n literales como output, lo cual hace que se
puedan generar muchos más outputs que los inputs que se consumen.

De hecho, podemos tener una situación en la cual haya máquinas que solo re-
transmiten lo que les llega a otra máquina. Por ejemplo, si F1 quisiera mandarle
dos literales, AB, a F2, podŕıa utilizar una máquina intermediaria F3: F1 mandaŕıa
A a F2 y B a F3, y después F3 retransmitiŕıa esa B para que le llegara a F2. De
esta forma, estaŕıamos consiguiendo mandar mensajes con más de un literal de F1

a F2 sin que nunca añadamos más de un literal a cada buffer en cada transición, lo
cual nos indica que el fenómeno de proliferación de los outputs es completamente



Caṕıtulo 5 - Definición general de los sistemas 17

inherente a la definición de estos sistemas, pues se puede conseguir incluso con la
limitación de que no se pueden generar outputs sin consumir inputs.

De esta forma, al ser la proliferación de los outputs un fenómeno tan inherente
a este tipo de sistemas, no nos debeŕıa molestar el hecho de que una FSM se pueda
mandar mensajes también a śı misma (que en principio podŕıa no parecer la mejor
opción), pues siempre podŕıamos introducir una máquina intermediaria con el mismo
propósito (como comentamos en el párrafo anterior). Por tanto, no tendŕıa sentido
limitar que una máquina no se pueda enviar mensajes a śı misma.

A la vista de lo anterior, queda claro que la única forma de evitar la proliferación
de los outputs en este tipo de sistemas es que cada transición genere a lo sumo un
output cada vez que consigue un input. Esto se daŕıa si δi : Qi × Ii −→ Qi ×(
O?
i

)n
funciona de forma que para cada transición δi(qi, α) = (q′i, α1, α2, . . . , αn) a

lo sumo una de las producciones α1, . . . , αn es distinto de ε. La única manera de
conseguir evitar el fenómeno de proliferación de los outputs seŕıa por tanto hacer
esta modificación de nuestra definición.

Por ello, al ser inherente a estos sistemas el fenómeno de proliferación de los
outputs, podemos modificar ligeramente la definición de las FSMs que usamos, de
forma que sean más cómodas de utilizar. En vez de considerar que la función de
transición de la máquina Fi es δi : Qi × Σ? −→ Qi ×

(
Σ?

)n
, podemos considerar

equivalentemente δi : Qi × Σ? −→ Qi × (Σ∗)n, lo cual nos simplificará algunos
razonamientos en caṕıtulos venideros. En realidad esto es simplemente una extensión
de los argumentos que comentábamos a la hora de definir sistemas con solo dos
FSMs, y que demostramos con mayor formalidad en el teorema 4.2, y por tanto no
creemos que sea necesario incidir más en ello.

Notemos asimismo que este tipo de sistemas son Turing completos, pues ya
hemos probado en el caṕıtulo anterior que una subclase suya, en la que restringimos
el número de máquinas a únicamente 2, ya es Turing completa (como vimos en el
teorema 4.2).

5.1. Sistemas con buffers acotados

Para poder seguir estableciendo comparativas que nos ayuden a comprender qué
caracteŕısticas de los sistemas de FSMs en comunicación son los que realmente le
dan su gran expresividad, vamos a estudiar otra modificación, en la que esta vez
hay una limitación en cuanto a la memoria que el sistema puede usar.

Definición 5.2. Decimos que un sistema de FSMs en comunicación S = (F1, F2, . . . , Fn)
es un sistema con buffers acotados si existe una constante M de manera que
en cada una de las configuraciones (q1, B1, q2, B2, . . . , qn, Bn) alcanzables de S, el
tamaño de cada buffer es a lo sumo M , es decir, |Bi| ≤M ∀ 1 ≤ i ≤ n.

Esta limitación podŕıa parecer excesiva una vez que nos damos cuenta de que en
realidad, dada la capacidad finita de los buffers, en realidad este tipo de sistemas
solo pueden recibir inputs de una longitud acotada por M (o Mn en caso de que



Caṕıtulo 5 - Definición general de los sistemas 18

distribuyéramos de alguna forma dichas instancias sobre los cuales el sistema se
ejecuta en los diferentes buffers). Esto haŕıa que los únicos lenguajes que se pudieran
reconocer con este tipo de sistemas fueran una subclase de los lenguajes finitos, un
estadio muy pobre en la jerarqúıa de Chomsky. Para evitar esta situación un tanto
indeseable, pues el hecho de que las máquinas estén en comunicación no añadiŕıa
nada a su capacidad expresiva, vamos a hacer una pequeña modificación. Podemos
considerar que hay una máquina F0 que es la que recibe los inputs del sistema,
y por tanto su buffer no está acotado, es una FSM normal. Pero si dejamos que
esta máquina participe en la comunicación con el resto de máquinas, realmente la
hipótesis de que los buffers están acotados no tendŕıa ya mucho sentido, pues se
podŕıa usar el de F0, que no lo es. Por tanto, debemos mantener a F0 al margen
de estas comunicaciones. Podemos imponer que lo único que haga F0 sea enviar
inputs poco a poco a (sin pérdida de generalidad) F1, siempre que B1 no esté lleno,
y que F0 no interactúe de ninguna otra manera dentro del sistema. En concreto,
no puede recibir mensajes de ninguna máquina. De esta forma, queda claro que
estamos respetando la restricción de los buffers acotados: todos los cómputos que
hace S utilizan solo los buffers acotados; mientras que el truco de añadir F0 no mejora
las caracteŕısticas de S, sino que solo permite que además se procesen palabras de
longitud arbitraria como input, lo cual es bastante más razonable para un modelo
de cómputo.



Caṕıtulo 6

Sistemas donde los outputs no
proliferan

Si reducimos la capacidad de comunicación de nuestros sistemas de FSMs no
permitiendo que proliferen los outputs como en las situaciones anteriores, tiene sen-
tido pensar que la expresividad de estos sistemas caerá, y puede que no estén como
en el caso anterior a la misma altura que las máquinas de Turing en la jerarqúıa
de Chomsky. Pero tampoco pierden demasiada expresividad, pues pueden recono-
cer lenguajes que no son incontextuales, como el de las palabras del tipo w#w, con
w ∈ Σ∗ para algún alfabeto no trivial, como por ejemplo Σ = {0, 1} (lo cual veremos
en más detalle a continuación). Esto nos sugiere buscar un estadio intermedio entre
los autómatas con pila y las máquinas de Turing, como los autómatas linealmente
acotados (LBA por sus siglas en inglés). En este caso, esta intuición va a ser co-
rrecta, pues va a existir una equivalencia de expresividad entre los LBA y nuestros
sistemas de FSMs donde los outputs no proliferan.

Recordamos brevemente la definición de un LBA:

Definición 6.1. Se dice que F = (Q,Γ, [, q0, QF , δ) es un LBA si es una máquina
de Turing (con estados Q, alfabeto Γ, śımbolo de blanco [, estado inicial q0, estados
de aceptación QF y función de transición δ : Q× Γ −→ Q× Γ× {←,→}) de forma
que a lo largo de toda la ejecución procesar un input solo utiliza una cantidad de
posiciones de su cinta que es lineal en el tamaño de dicho input.

Es decir, ante un input de tamaño n, un LBA solo puede utilizar una cantidad
O(n) de posiciones de su cinta; y por lo demás se comporta como una máquina
de Turing usual. En concreto, se suelen usar śımbolos delimitadores como `,a en
ambos extremos de la cinta para que quede claro que la cantidad de cinta que se
puede usar está acotada desde el principio. Se puede consultar más sobre ellos en,
por ejemplo, el caṕıtulo 9.3 de [17].

6.1. Ejemplo de funcionamiento

Vista la anterior intuición sobre en qué nivel de la jerarqúıa de Chomsky podŕıan
situarse los sistemas de FSMs en los cuales los outputs no proliferan, consideramos
útil desarrollar más el ejemplo anterior para ver más en detalle un ejemplo en el
cual la comunicación que se establece entre dos FSMs sencillas es suficiente para
reconocer un lenguaje un tanto complejo, que no es incontextual.

19



Caṕıtulo 6 - Sistemas donde los outputs no proliferan 20

Proposición 6.2. El lenguaje L =
{
w#w : w ∈ {0, 1}∗

}
no es incontextual, pero

puede ser reconocido por un sistema de FSMs en comunicación donde los outputs
no proliferan.

Demostración. Demostramos los dos asertos por separado:

L no es incontextual. Lo demostramos con una aplicación del lema del bombeo.
Suponiendo que L fuera incontextual, sea n es la constante del lema del bom-
beo de L. Considerando la palabra 0n1n#0n1n ∈ L, tendŕıa que admitir una
descomposición 0n1n#0n1n = uvwxy, con |vwx| ≤ n,|vx| ≥ 1. Demostrare-
mos que uv2wx2y /∈ L para cualquiera de estas descomposiciones (llegando por
tanto a una contradicción). Como # no se puede duplicar sin que la palabra
salga de L, tenemos 3 opciones:

1. # ∈ w. En ese caso, como |vwx| ≤ n, tenemos que v = 1a, x = 0b, donde
al menos uno de entre a y b es estrictamente positivo por ser |vx| ≥ 1.
Si a > 0, en uv2wx2y se descompensarán los unos en la palabra de la
izquierda; y si b > 0, los ceros en la de la derecha. De ambos modos,
uv2wx2y /∈ L.

2. # está en u o más a su izquierda. Entonces en uv2wx2y será forzosamen-
te más larga la palabra de la derecha, pues solo se bombea en ella. Y
necesariamente uv2wx2y /∈ L.

3. # está en y o más a su derecha. Es una situación análoga al punto ante-
rior.

Pero, de hecho, podemos encontrar un sistema de FSMs en el cual los outputs
no proliferan y que reconoce este lenguaje. Nuestro sistema será S = (F1, F2).
F1 irá reconociendo las letras de la primera palabra, una a una, e irá confir-
mando que están en el mismo orden en la segunda palabra con la ayuda de
F2, que irá resaltando las letras con las que debeŕıan coincidir. Un ejemplo de
máquinas que podŕıan hacer esta tarea seŕıan las siguientes:

1. Máquina F1: lo primero que hace es insertar [ para simbolizar el fin de las
palabras. Su funcionamiento es el siguiente: hace un barrido del buffer hasta
que reconoce la primera letra (la de después de [), y entra en un estado especial
donde la recuerda, y la quita del buffer. Espera hasta que F2 le manda una
letra con barra arriba (que serán nuevos literales del alfabeto en los cuales nos
apoyaremos en la construcción), que es la confirmación de que después de #
ha venido esa letra. Si coincide con lo que recordaba, vuelve a empezar el ciclo,
hasta que los buffers se vaćıan, y en ese momento reconoceŕıa [#[ y aceptaŕıa.
Una versión gráfica de la implementación la podemos encontrar en 6.1.



Caṕıtulo 6 - Sistemas donde los outputs no proliferan 21

q q[

q0

q1

qf q′f qini
[/[

0/ε

1/ε

#/# [/[

0̄/ε

1̄/ε

0/[

1/[

x/x (x 6= 0̄)

x/x (x 6= 0̄)

x/x (x 6= 0̄)

Figura 6.1: Representación gráfica de la máquina F1.

2. Máquina F2: su funcionamiento es el siguiente: hace un primer barrido hasta
que llega a #, y marca el siguiente literal con una barra para que la máquina
1 lo reconozca. Después recorre la longitud de un buffer completo esperando
a que la máquina 1 reconozca el literal que acaba de marcar. Tras esto, repite
el ciclo que explicábamos, y vuelve a marcar lo que aparezca después de #.
Gráficamente podemos pensar la implementación de esta FSM como en 6.2.

q q# q′
#/#

#/#

x/x (x 6= #) x/x (x 6= #)

0/0̄

1/1̄

Figura 6.2: Representación gráfica de la máquina F2.

6.2. Expresividad de los sistemas donde los outputs no
proliferan

Veamos ahora que, de hecho, los sistemas de FSMs en comunicación en los cua-
les no se permite el fenómeno de proliferación de outputs solo pueden reconocer
lenguajes dependientes del contexto, pues pueden ser simulados por LBAs.



Caṕıtulo 6 - Sistemas donde los outputs no proliferan 22

La idea detrás de la demostración es que los autómatas linealmente acotados se
ajustan perfectamente a esta situación, pues en ellos la información que hay en la
cinta tiene siempre la misma longitud, y esa es exactamente la situación que nos
encontramos en nuestro sistema de FSMs. En concreto, guardaremos la información
de todos los buffers dentro de la cinta de nuestro LBA.

Para hacer el razonamiento más claro y comprensible, vamos a considerar primero
el caso de que tenemos un sistema de dos FSMs en comunicación. Después quedará
claro que el razonamiento se puede hacer extensible al caso general.

Proposición 6.3. Los sistemas de 2 FSMs en comunicación en los cuales los out-
puts no proliferan pueden ser simulados por LBAs.

Demostración. Sea S = (F1, F2) nuestro sistema de FSMs, con buffers B1, B2.
Vamos a construir un LBA F = (Q,Γ, [, q0, QF , δ) que simule el comportamiento
de este sistema. La cinta de F tendrá siempre la información de B1 y B2: será una
concatenación de ambos buffers, con un śımbolo especial separador entre los dos
(denotado aqúı por # ∈ Γ \ Σ), y con otros dos śımbolos especiales que denotarán
el inicio y el final de la franja usable de la cinta. Recordemos que en un LBA solo
podemos usar una cantidad lineal en el número de posiciones de la cinta que ocupe
el input inicial, aśı que lo rodearemos con estos śımbolos: `∈ Γ \Σ marcará el inicio
y a∈ Γ \ Σ, el final. La forma de la cinta seŕıa entonces la siguiente: ` B1#B2 a.
Para ser coherentes con la representación indexada que definimos de los buffers, B1

y B2 están mapeados de izquierda a derecha según crecen sus ı́ndices.

Podemos suponer igualmente que la situación inicial de la cinta de F es exacta-
mente ` B1#B2 a, donde B1, B2 son los buffers al inicio de la ejecución, pues esto
no supone una complejidad de cálculo alguna.

Pasemos ahora a ver más en detalle cómo se construye F . Como comentábamos,
Γ := Σ∪{`,a,#, [}. Para cada par de estados (qi, qj) ∈ Q1×Q2, F tendrá un estado
qi,j que lo simula. Para simular cada transición de S necesitaremos hacer recorridos
por la cinta de F para modificarla de manera acorde con los contenidos de los
buffers B1, B2. Para que estas modificaciones de la cinta sean correctas, usaremos
una serie de estados auxiliares: al simular una transición de F1 que transita de qi a
qi′ , mientras que F2 está en el estado qj , tendremos un conjunto de estados auxiliares
del tipo qi→i′,j (que variarán dependiendo del tipo de transición, como veremos en
unas ĺıneas). De manera análoga se generarán estados del tipo qi,j→j′ para simular
transiciones de F2.

Vamos a ver ahora de forma más detallada cómo son las construcciones concretas
que hacen que F pueda simular el sistema S:

Por cada transición δ1(qi, a) = (qi′ , b) de F1, con b 6= ε, tendremos que trans-
formar, cuando sea posible (es decir, cuando haya una a al inicio de la zona
donde representamos B1 en la cinta), el estado de la cinta de ` aα#β a a
` α#βb a. Esto es un sencillo ejercicio de programación en autómatas, que
se puede resolver de la siguiente forma ayudándonos de ciertos estados au-
xiliares: simplemente desplazamos el contenido de toda la cinta una posición
a la izquierda, siguiendo el bucle de los estados q1

i→i′,j y los estados del tipo



Caṕıtulo 6 - Sistemas donde los outputs no proliferan 23

qx,0i→i′,j , q
x,1
i→i′,j , con x recorriendo Γ; y hecho todo este recorrido, ponemos una

b al final de la cinta, en la posición correspondiente al final de B2. Este diseño
es como ilustra la figura 6.3.

qi,j q0
i→i′,j q1

i→i′,j

qx,0i→i′,j

q2
i→i′,j

qx,1i→i′,j

qi′,j

` / `,→

x/x,← (x 6=`)

a/a,→

x/x,←
(x 6=a)

y/x,→ (∀y)

x/x,→

a / a,←

z/b,← (∀z)

Figura 6.3: Representación gráfica de la implementación de una transición del tipo
δ1(qi, a) = (qi′ , b).

En el caso de que tengamos una transición de F1 que no genere un literal como
output, es decir, δ1(qi, a) = (qi′ , ε), la situación es muy similar: basta repetir
el bucle de la construcción precedente, y terminar desplazando el śımbolo a
también una posición a la izquierda, como ilustra la figura 6.4.

qi,j q0
i→i′,j q1

i→i′,j

qx,0i→i′,j

q2
i→i′,j

qx,1i→i′,j

qi′,j

` / `,→

x/x,← (x 6=`)

a/a,→

x/x,←
(x 6=a)

y/x,→ (∀y)

x/x,→

a /[,←

z/ a,← (∀z)

Figura 6.4: Representación gráfica de la implementación de una transición del tipo
δ1(qi, a) = (qi′ , ε).



Caṕıtulo 6 - Sistemas donde los outputs no proliferan 24

Por cada transición δ2(qj , a) = (qj′ , b) de F2, con b 6= ε tenemos igualmente
que transformar (cuando la configuración de la cinta sea adecuada, es decir,
cuando la región donde está B2 no esté vaćıa y tenga una a al principio) la
cinta de ser ` α#aβ a a ` αb#β a. Esto es un ejercicio más sencillo aún que
el anterior, pues básicamente se trata de encontrar el delimitador central # y
hacer un par de cambios a su lado, como se puede comprobar en el diagrama
6.5.

qi,j q0
i,j→j′ q1

i,j→j′ q2
i,j→j′

qi,j′

` / `,→

x/x,← (x 6=`)

#/#,→

x/x,→ (x 6= #)

a/#,←

#/b,→

Figura 6.5: Representación gráfica de la implementación de una transición del tipo
δ2(qj , a) = (qj′ , b).

Y por último, tratamos el caso de que tengamos una transición de F2 que no
produzca outputs: si tenemos una transición δ2(qj , a) = (qj′ , ε), tenemos que
trasladar la región de la cinta asociada a B2 hacia la izquierda, para borrar el
literal que estaba en su primera posición. Esto se puede hacer con un esquema
muy similar al bucle que nos encontrábamos al simular los movimientos de F1,
como podemos comprobar gráficamente en la figura 6.6.



Caṕıtulo 6 - Sistemas donde los outputs no proliferan 25

qi,j q0
i,j→j′ q1

i,j→j′ q2
i,j→j′

q3
i,j→j′

qx,0i,j→j′ qx,1i,j→j′

qi,j′

` / `,→

x/x,← (x 6=`)

#/#,→

x/x,→ (x 6= #)

a/#,→

x/x,←
(x 6=a)

y/x,→ (∀y)

x/x,→

a /[,←

z/ a,← (∀z)

Figura 6.6: Representación gráfica de la implementación de una transición del tipo
δ2(qj , a) = (qj′ , ε).

Por último hemos de comentar que los estados finales de nuestro LBA F serán
simplemente aquellos estados qi,j que simulen una configuración de estados (qi, qj) ∈
Q1 ×Q2 que sea de aceptación en S.

De esta forma, es claro que, dada la construcción que hemos hecho, hay una
ejecución de F de forma que su cinta va reflejando exactamente el contenido de
los buffers B1 y B2 a lo largo de cualquier ejecución del sistema S. Además, la
cinta de F solo utiliza una cantidad limitada de cinta: como podemos ver en los
diferentes casos que hemos ido desgranando, la distancia máxima entre los śımbolos
` y a en la cinta de F , que reflejan la cantidad de cinta que F usa, se da al inicio,
pues esa distancia nunca aumenta (y de hecho puede disminuir si nos encontramos
con alguna transición que no genera outputs en S). Por tanto, el autómata F que
hemos definido es realmente un LBA, como queŕıamos comprobar. Por tanto, hemos
conseguido simular un sistema de FSMs mediante un LBA, y de ah́ı deducimos que
estos sistemas de FSMs en los cuales los outputs no proliferan no pueden reconocer
más que los lenguajes dependientes del contexto.

Además, la reducción que hemos hecho tiene buenas propiedades: la cantidad
de estados que tiene F es polinómica con respecto a la que tienen F1 y F2 juntas:
por cada par (qi, qj) ∈ Q1 × Q2 tenemos un estado en F . Y además, por cada una
de las transiciones que pueden salir de este estado (hay a lo sumo 2|Σ| posibles),
tenemos una cantidad acotada de estados auxiliares, a lo sumo 4 + 2|Γ|. Por tanto,
la cantidad de estados que hay en F la podemos acotar de la siguiente forma:

|Q| ≤ |Q1| · |Q2| · (2|Σ| (4 + 2|Γ|)) ∈ O(|Q1| |Q2|) ⊂ O((|Q1|+ |Q2|)2)

que es una cantidad polinómica en la cantidad de estados de S, |Q1|+ |Q2|.

Además, el tiempo que tarda F en simular una ejecución de S es también po-
linómico. Notemos que para simular cualquier transición de S, F pasa por cada



Caṕıtulo 6 - Sistemas donde los outputs no proliferan 26

elemento de la cinta a lo sumo 3 veces (que recordemos que tiene un tamaño aco-
tado por su tamaño inicial). Por tanto, visita una cantidad acotada de estados por
cada transición que toma S, y esto resulta en que la reducción es también polinómica
en cuanto a tiempos de ejecución.

Con lo anterior quedaŕıa completa la prueba para el caso de que el sistema de
FSMs en comunicación tuviera únicamente 2 máquinas. Pero el razonamiento en el
caso de que hubiera n máquinas seŕıa bastante similar, como vamos a comprobar.

Teorema 6.4. Cualquier sistema de FSMs en comunicación en el cual los outputs
no proliferan puede ser simulado por un LBA.

Demostración. Teniendo en mente la demostración del caso en el que teńıamos
únicamente 2 FSMs, vamos a esbozar las modificaciones que permiten demostrar
el caso general. En este caso, en lugar de que F tenga estados formados por pa-
res, tendrá estados que ser n-tuplas qi1,i2,...,in , que se encargaŕıa de la simulación
de la configuración del sistema cuando F1 está en el estado qi1 , F2 en el qi2 , y aśı
sucesivamente. Asimismo, dada una transición en la máquina Fk del estado qik al
estado qi′k , usaŕıamos estados auxiliares qi1,...,ik−1,ik→i′k,ik+1,...,in . Estos estados auxi-
liares ayudaŕıan a modificar la cinta, que contendŕıa el contenido de los n buffers
uno detrás de otro: ` B1#B2# · · ·#Bn a.

Las transiciones del tipo δi(qi, a) = (qi′ , ε, ε, . . . ,
pos. j

b , . . . , ε), que hacen que la
máquina Fi ponga un literal b en el buffer de Fj , se simulaŕıan del siguiente modo.
Supongamos primero que i > j. En este caso, primero tendŕıamos que encontrar
la posición del i-ésimo buffer en la cinta, y para eso hacemos un bucle en el cual
contamos i − 1 vistas de # según avanzamos hacia la derecha, y con un paso más
llegamos a la a. Hecho esto, nos desplazamos a la izquierda hasta que veamos i−j−1
veces el literal #, y vamos copiando cada posición a su derecha, para simular el
borrado de la a. Una vez lleguemos a la posición donde estaba la i− j − 1-ésima #,
ponemos la b, y ya quedaŕıa modificado convenientemente el buffer. En el caso de
que i ≤ j, tendŕıamos que avanzar hacia la derecha copiando literales en su posición
de la izquierda, pero el esṕıritu del proceso seŕıa el mismo.

Es sencillo darse cuenta de que esta construcción, a pesar de ser un poco más
compleja en cuanto a notación, funciona por el mismo motivo que lo haćıa la anterior,
pues el modo de razonar es exactamente el mismo. Igualmente el tamaño de la cinta
de F nunca crece porque la cantidad de literales que hay en un sistema de FSMs
donde los outputs no proliferan tampoco crece; y por tanto F es un LBA.

Además, si consideramos n (el número de FSMs de nuestro sistema) prefijado,
todas las construcciones que hemos comentado siguen siendo de tipo polinómico en
cuanto al número de estados se refiere (aunque esta vez polinomios de grado n en
vez de cuadráticos, claro), y siguen siendo también del mismo orden de complejidad
en cuanto a tiempo de ejecución (este no depende de n), aśı que las generaliza-
ciones naturales de la primera construcción heredan de alguna forma estas buenas
propiedades.

Sabiendo ya que estos sistemas pueden reconocer únicamente lenguajes depen-
dientes del contexto, vamos a afinar más. Ahora vamos a comprobar que este tipo de



Caṕıtulo 6 - Sistemas donde los outputs no proliferan 27

sistemas no pertenece a ningún nivel inferior de la jerarqúıa de Chomsky pues, como
vamos a demostrar, pueden simular cualquier LBA. Por tanto, son completos dentro
de los autómatas dependientes del contexto. Veamos ahora esta demostración.

Cabe destacar que en este caso utilizaremos una definición un tanto distinta de
los LBA, pues hay una definición equivalente que restringe la cantidad de cinta que
puede usar un LBA a únicamente la que ocupa su input inicial. Esta versión, en la
cual no permitimos una cantidad lineal de cinta extra, es equivalente, en términos
de capacidad de cómputo, a la que propusimos anteriormente al definir los LBAs
como consecuencia del Teorema del linear speedup en máquinas de Turing (se puede
consultar en [17], caṕıtulos 9.3, 12.2).

Teorema 6.5. Cualquier LBA puede ser simulado por un sistema de FSMs en
comunicación donde los outputs no proliferan.

Demostración. Sea F = (Q,Σ, [, q0, QF , δF ) un LBA. Vamos a definir un sistema
S = (F1, F2) de FSMs donde los outputs no proliferan que simule F . F2 será una
máquina muy sencilla, que simplemente devuelve todo literal que le llega. Podŕıamos
representarla del siguiente modo que nos muestra la siguiente figura:

q x/x (∀x)

Figura 6.7: Representación gráfica de F2.

La máquina F1 llevará toda la complejidad de simular F . Como F es esencial-
mente una máquina de Turing usual, tiene una cinta, que intentaremos mantener
en B1. Pero F tiene además un cabezal que puede modificar literales de cualquier
posición de la cinta, mientras que F1 solo puede tomar literales desde el principio
de su buffer B1. Esto genera una dificultad, pero que se solventa de manera sencilla,
como usualmente en estas situaciones: iterando sobre todo el buffer B1 cada vez que
F dé un paso. De esta manera, aunque de una forma un poco costosa, podemos
simular cada movimiento de F con la generación de un nuevo buffer B1, que será la
cinta de F en el siguiente instante de tiempo.

Además, a la hora de simular esta cinta, aparecen ciertas dificultades. La primera
es la de simular el cabezal de F . Lo solventaremos simplemente introduciendo más
literales: por cada γ ∈ Σ, el nuevo literal γ̄ ∈ Γ del alfabeto de S significará que en
el buffer hay una γ y además en el cabezal está justo en esa posición.

Se nos presenta también la dificultad de que el cabezal de F puede avanzar
hacia la izquierda y a la derecha en la cinta, mientras que nuestra máquina F1 solo
puede leer su buffer en una dirección (digamos que de izquierda a derecha). La
idea para solventar esto es simplemente retrasar un ciclo todas las decisiones de F1,
pues aśı nunca tomaremos decisiones incorrectas del siguiente tipo: si teńıamos αβ̄
y tenemos que simular un movimiento a la izquierda del cabezal en una transición
del tipo δ(q, β) = (q′, γ,←), estos literales tendŕıan que pasar a ser ᾱγ; pero solo
nos damos cuenta de que α tendrá el cabezal encima una vez que hemos visitado



Caṕıtulo 6 - Sistemas donde los outputs no proliferan 28

β y hemos visto que ella śı tiene el cabezal encima. Un esquema visual de estas
producciones atrasadas seŕıa el siguiente (ati denota el i-ésimo carácter de la cinta
en el instante t, y las flechas discontinuas denotan con la lectura de qué literal se
generan otros literales):

a0
0 a0

1 a0
2 a0

3 a0
4 a0

5

a1
0 a1

1 a1
2 a1

3 a1
4 a1

5

a2
0 a2

1 a2
2 a2

3 a2
4 a2

5

Figura 6.8: Ejemplo explicativo de en qué momento se lleva a cabo cada producción.

Además tenemos que conseguir este retraso en la ejecución sin que proliferen
los outputs, lo cual no es inmediato de conseguir en una primera aproximación al
problema. Esto se puede solucionar introduciendo un carácter # que indique el fin
de la cinta de F en nuestros buffers (es decir, que separe los buffers que se refieren
a diferentes instantes de tiempo), lo cual sigue la idea de los LBA de delimitar la
memoria que podemos utilizar.

Con estas ideas en mente, pasemos a la implementación de manera más concreta
de la máquina F1. Lo primero es comentar que el alfabeto que usará el sistema S
será, como antes se indicaba: Γ := Σ ∪ {γ̄ : γ ∈ Σ} ∪ {#}.

Para cada estado qi ∈ Q de F tendremos un cluster de estados en F1 que si-
mularán un barrido de la cinta de F mientras está en el estado qi, cuyos estados
denotaremos qi (además de más sub́ındices para indicar la función de esos estados
dentro del cluster). En cada uno de estos clusters tenemos que implementar la idea
anterior de retrasar la producción de outputs un ciclo, aśı que tendremos que tener
un estado diferente para cada literal de Γ para recordar cuál es el literal que aca-
bamos de ver. Además, tenemos que conseguir simular las transiciones de F . Por
ejemplo, si en F hay una transición de qi a qj cuando el cabezal ve una A, nuestra
máquina F1, en su cluster relativo a qi, tendrá una transición diferente cuando vea
Ā, pues transitará hacia una región diferente del cluster en la cual recordaremos que
el siguiente estado al que va a ir F es qj . De esta forma, cuando le llegue la siguiente
#, F1 transitará hacia el cluster relativo a qj , y comenzará de nuevo a barrer la
cinta de F leyendo de su buffer.

Para poder cumplir esto, cada cluster qi tendrá un conjunto de estados qγi , con
γ ∈ Σ ∪ {#}, de forma que ejecutan la creación del nuevo buffer antes de que se
haya visitado la posición donde está el cabezal lector (es decir, van devolviendo
exactamente lo que leen, pero un ciclo más tarde). Posteriormente, al ver el cabezal,
hemos de distinguir si las diversas transiciones de F en qi mueven el cabezal a la



Caṕıtulo 6 - Sistemas donde los outputs no proliferan 29

izquierda o a la derecha, pues se nos generará una estructura diferente de estados
en cada caso.

Por ejemplo, si en F tenemos una transición que mueve el cabezal lector hacia
la izquierda, del tipo que nos muestra la siguiente figura:

qi qj
a/b,←

Figura 6.9: Representación gráfica de un ejemplo de transición que mueve el cabezal
a la izquierda.

Tenemos por tanto que tener una estructura de estados dentro del cluster asocia-
do a qi que pueda solventar esta situación. Tendremos para ello un estado q0

i→j que
visitaremos justo cuando hayamos visto el cabezal con una A, y que nos ayudará a
transitar hacia una zona del cluster donde recordamos que el siguiente estado que
visitará F es qj . Una vez visitado q0

i→j , nos encontramos con otra región del cluster
donde lo único que hacemos es copiar el buffer para la siguiente iteración, al igual
que haćıamos con los estados del tipo qγi . Por eso llamamos a estos estados qγi→j ,
pero esta vez únicamente con γ ∈ Σ, pues la llegada de una # nos hará transitar
hacia el cluster asociado a qj . Suponiendo, por simplicidad para la representación
gráfica, que Σ = {a, b} (una vez visto el diagrama quedará claro que es sencillo
generalizarlo a un alfabeto con más literales), podŕıamos plasmar estas ideas sobre
el cluster de qi de la forma que nos indica la figura 6.10.

q#
i

de otros
clusters

qai

qbi

q0
i→j

qai→j

qbi→j

q#
j

cluster de
qj . . .

a/#

b/#

b/a

a/b

a/a

b/b

ā/ā

ā/b̄

a/b

b/b

b/a a/b

a/a

b/b

#/a

#/b

Figura 6.10: Representación gráfica de la implementación de un cluster simulando
transiciones que mueven el cabezal hacia la izquierda.



Caṕıtulo 6 - Sistemas donde los outputs no proliferan 30

Y, en cambio, si la transición de F mueve el cabezal a la derecha, tenemos que
introducir algunos estados más para recordar los literales que vemos durante este
movimiento. Supongamos entonces que tenemos en F tenemos la transición entre
qi, qj ∈ Q, del tipo de la figura siguiente:

qi qj
a/b,→

Figura 6.11: Representación gráfica de un ejemplo de transición que mueve el cabezal
a la derecha.

Entonces en F tendremos que tener una estructura del estilo de la mostrada en la
figura 6.12 dentro del cluster relativo a q1, que es bastante similar a la anterior, pero
donde introducimos algunos estados más q1,γ

i→j , con γ ∈ Σ para recordar los literales
que vemos justamente al llegar al cabezal (de nuevo supondremos Σ = {a, b} por
simplicidad del diagrama):

q#
i

de otros
clusters

qai

qbi

q0
i→j

q1,a
i→j

q1,b
i→j

qai→j

qbi→j

q#
j

cluster de
qj . . .

a/#

b/# a/a

b/b

b/a

a/b

ā/a

ā/b

a/b

b/b

a/ā

b/ā

a/b̄

a/b̄

b/a

a/b

a/a

b/b

#/a

#/b

Figura 6.12: Representación gráfica de la implementación de un cluster simulando
transiciones que mueven el cabezal hacia la derecha.

Naturalmente, desde un estado qi de F podŕıa darse el caso de que hubiera
transiciones a más de un estado del tipo qj en los ejemplos anteriores. Esto haŕıa



Caṕıtulo 6 - Sistemas donde los outputs no proliferan 31

que nuestro cluster asociado a qi fuera más grande, ya que para cada transición de
qi a qj , el cluster debeŕıa contener una estructura de estados qi→j . Es decir, dentro
de un mismo cluster, tendremos que tener tantas estructuras del tipo qi→j como
transiciones tenga F en qi.

De esta forma, en el cluster del estado qi de F tenemos una columna de estados
en los cuales no hemos visto todav́ıa la posición del cabezal (los qγi , después una
serie de estados (un conjunto de estados por cada transición saliente de qi en F )
que manejan el tratamiento del literal con el cabezal y la transición de F (los q0

i→j ,

q1,γ
i→j), y una serie de columnas de estados (también una por cada transición de qi)

que recuerdan a qué estado transita F y, por tanto, cuál es el siguiente cluster al
que irá F1 (los estados del tipo qγi→j).

Aśı podemos ir simulando transiciones de F , que modifican un par de posiciones
de la cinta, con un recorrido dentro de uno de los clusters de F1, que genera un
nuevo buffer simulando la cinta de F , y se la env́ıa a F2. F2, por su parte, reenv́ıa
el buffer a F1 para que pueda efectuar la siguiente transición.

Es importante hacer hincapié en el inicio de todo este procedimiento: al principio,
el input de F se pone en el buffer B1 (sin ninguna modificación), y el estado inicial

de F1 es q#
0 (recordemos que el estado inicial de F era q0). Aśı, lo primero que

hará F1 será generar una #, lo cual le ayudará a distinguir ese buffer del que se
corresponderá al siguiente estado de la cinta de F . Después seguirá tratando los
literales de B1 con total normalidad, empezando en el cluster de q0, claro.

Y simular el criterio de aceptación de F también es sencillo: simplemente tenemos
que hacer que (qi, q) ∈ Q1 × Q2 sea de aceptación siempre que qi represente en F1

un estado final de F , es decir, qi ∈ QF ⊆ Q.

De esta forma, hemos hecho una reducción del LBA F a un sistema de FSMs en el
cual los outputs no proliferan, como hemos comprobado a la hora de construirlos.

Además, en el sistema de FSMs que hemos construido, el número de estados es
polinómico con respecto a los de F :

|QF1 | = #clusters ·#estados por cluster
≤ |QF | ·

(
(|QF |+ 1) · (|ΣF |+ 1) + 1 + |ΣF |+ 1

)
∈ O

(
|QF |2

)
Esto demuestra que la creación del sistema de FSMs en función de F se puede

hacer con una cantidad de estados polinómica respecto al tamaño de F . Además,
la reducción, en cuanto a tiempos de ejecución, también es polinómica: si tenemos
un input de longitud n y, para procesar dicho input, F da k pasos; entonces nuestro
sistema S, por cada uno de estos k pasos recorrerá la cinta entera de F dos veces
(una será por un recorrido de F1 y otra por el de F2). Pero como F es un LBA, el
tamaño de la cinta siempre está acotado por n. Es decir, el sistema S dará O(nk)
pasos en su ejecución. Por tanto, podemos afirmar que la reducción es polinómica y
no se añade por tanto un sobrecoste reseñable.



Caṕıtulo 7

Sistemas con buffers acotados

Otro caso que podemos estudiar es el de un sistema de FSMs en comunicación
en el cual los buffers, por alguna razón, tienen tamaño acotado desde el principio,
como definimos en el apartado 5.1. Esto supone una limitación similar a la estudiada
en el caso de que los outputs no proliferaran en el sentido de que estamos limitando
la expresividad de nuestro sistema. En el caso de que los outputs no proliferaran ya
estudiamos que el sistema dejaba de ser Turing completo, y se quedaba en un estadio
un poco anterior de la jerarqúıa de Chomsky, el de los lenguajes dependientes del
contexto. En este caso, vamos a ver sin mucha dificultad que podemos comprobar
que la limitación de la expresividad es mucho más potente, y este tipo de sistemas se
van a quedar en lo más bajo de la jerarqúıa, en los lenguajes regulares. Esto se debe
a que la información que potencialmente puede tener el sistema es en cualquier caso
finita, pues las FSMs involucradas lo son, y los buffers también. Esto contrasta con
el caso anterior por una sutileza: cuando no proliferaban los outputs, la información
estaba acotada dependiendo del tamaño inicial del input, pero como el tamaño inicial
del input no está acotado de antemano, la cantidad de información que teńıan esos
sistemas es mucho mayor que la de los sistemas que pasamos a estudiar ahora.

Vamos a proceder a simular un sistema de FSMs con buffers acotados mediante
un autómata finito. Esto demostraŕıa que nuestro sistema de FSMs como mucho
puede reconocer lenguajes regulares. Pero como, en concreto, el sistema está forma-
do por FSMs, que son autómatas finitos, también el sistema puede simular cualquier
autómata finito, y esto demuestra la equivalencia entre ambos modelos. La conclu-
sión clara es que añadir buffers acotados a unas FSMs para que se comuniquen entre
ellas no añade en ningún caso expresividad.

Teorema 7.1. Cualquier sistema de FSMs en comunicación con buffers acotados
puede ser simulado por un autómata finito.

Demostración. Sea S = (F0, F1, F2, . . . , Fn) un sistema de FSMs en comunicación
con buffers acotados, con buffers B0, B1, B2, . . . , Bn. Recordemos que esto significa
que existe un M prefijado de forma que la longitud de todos los buffers (excepto B0,
que corresponde a la máquina especial F0 según definimos en la sección 5.1) está
siempre acotada por M . Digamos que el alfabeto común de S es Σ, y con él definimos
Σ≤M := {w ∈ Σ∗ : |w| ≤M}, que nos ayudará a simplificar las expresiones relativas
a los buffers. Además, las máquinas serán Fi = (Qi, Ii, Oi, q

0
i , δi), con 0 ≤ i ≤ n, y

Ii, Oi ⊆ Σ, naturalmente.

Definamos ahora el autómata finito F = (Q,Σ, q0, QF , δ) que los simulará.
La clave está en hacer Q = Q1 × Σ≤M × Q2 × Σ≤M × · · · × Qn × Σ≤M , que

32



Caṕıtulo 7 - Sistemas con buffers acotados 33

simulará por completo el estado del sistema S de la siguiente forma: el estado
(q1, α1, q2, α2, . . . , qn, αn) ∈ Q simbolizará que F1 está en el estado q1, F2, en q2,
y aśı sucesivamente; y que el buffer B1 tiene por contenido la palabra α1, B2 tiene
la palabra α2, y aśı sucesivamente. Notemos que algunas de las posiciones de los
buffers pueden estar vaćıas, pues no necesariamente |αi| = M , sino que en general
tendremos |αi| ≤M por ser palabras de Σ≤M .

Como vemos, el alfabeto será Σ, el mismo que teńıa S, lo cual es necesario para
que F pueda aceptar los mismos śımbolos. Para cada śımbolo γ ∈ Σ que marque
una transición de F , querremos que signifique que la máquina F0 introduce en ese
instante el siguiente literal del input inicial, que esta vez será γ, dejándolo en el
final del buffer B1, claro. Pero en cada estado de F habrá más transiciones: aquellas
que pueda dar el sistema S sin consumir literales del input (y por eso F consumirá
únicamente ε), y que reflejan que una máquina Fi, con i ≥ 1, ha dado un paso en
su ejecución.

Nos falta definir la función de transición δ de F , lo cual es sencillo a partir de las
ideas anteriores. Tenemos que entender cómo reacciona ante los diferentes literales
de Σ, aśı que pasamos a definir estas transiciones.

Supongamos que estamos en un estado arbitrario (q1, α1, q2, α2, . . . , qn, αn) ∈ Q.
Veamos cuáles son las diferentes transiciones que tiene este estado en F .

Para los literales γ ∈ Σ, tenemos que añadir γ a B1 en caso de que este buffer
no esté lleno.

|α1| < M =⇒ δ((q1, α1, q2, α2, . . . , qn, αn), γ) = (q1, α1 + γ, q2, α2, . . . , qn, αn)

Para las transiciones que se toman con ε, tenemos que simular una transición
de la máquina Fi, para cada 1 ≤ i ≤ n. Esta transición dependerá de head(αi)
(en caso de que el buffer Bi no esté vaćıo). Digamos que la transición es la
siguiente: δi(qi, head(αi)) = (q′i, β1, β2, . . . , βn), donde q′i ∈ Qi es el estado de
llegada y βj ∈ Σ? es lo que se añade a Bj para 1 ≤ j ≤ n (recordemos que
F0 no participa en la comunicación, aśı que por simplicidad la omitimos). La
transición será posible en caso de que ninguno de los buffers exceda su tamaño
al añadir estos literales, lo cual podemos expresar de la siguiente forma:

|αi| > 0 ∧ αi =X + α′i

∧ δi(qi, X) = (q′i,β1, β2, . . . , βn)

∧ |αj + βj | ≤M ∀ 1 ≤ j ≤ n con i 6= j =⇒
(q1, α1 + β1, q2, α2 + β2, . . . , q

′
i, α
′
i + βi, . . . , qn, αn + βn)

∈ δ((q1, α1, q2, α2, . . . , qi, αi, . . . , qn, αn), ε)

Por último, comentar el estado inicial de la máquina F . Simplemente seŕıa el
estado (q0

1, ε, q
0
2, ε, . . . , q

0
n, ε). Y naturalmente, los estados de aceptación de F serán

aquellos en los cuales (q1, q2, . . . , qn) sea una configuración de aceptación de S.

Con este sencillo procedimiento queda claro que el autómata F (finito) que hemos
definido simula el comportamiento de S, pues simula cada uno de los pasos que puede
tomar en cada una de sus configuraciones.



Caṕıtulo 7 - Sistemas con buffers acotados 34

Además la reducción es polinómica conforme crece el tamaño de las máquinas
del sistema S: si S tiene k estados (es decir, |Q1|+ |Q2|+ . . .+ |Qn| = k), entonces
F tiene, a lo sumo, con una aproximación näıve, (kM)n estados, lo cual es una
cantidad polinómica en k, supuesto que el número n de máquinas que conforman S
y la constante que acota los buffers M son conocidas de antemano.



Caṕıtulo 8

Sistemas con buffers sin orden

Otra modificación posible de los sistemas de FSMs en comunicación residiŕıa en
modificar el funcionamiento de los buffers. Hasta ahora, siempre han estado imple-
mentados en forma de cola, de forma que los literales siempre quedaban ordenados
conforme a su momento de llegada. Ahora vamos a estudiar la situación en la cual
este orden se perdiera, por ejemplo por las caracteŕısticas f́ısicas de nuestro sistema,
que podŕıa no soportar estructuras de tipo cola o simplemente estructuras ordena-
das, o porque el protocolo usado no permite asegurar que se respete el orden de
llegada a los buffers. Se nos plantea entonces la siguiente modificación: si el conte-
nido de los buffers puede ser representado por multiconjuntos en lugar de colas, es
decir, estos buffers pertenecen a Σ⊕ (recordemos que X⊕ es la clase de multiconjun-
tos finitos con elementos en X) en vez de a Σ∗ (donde Σ es el alfabeto del sistema),
¿qué caracteŕısticas tienen estos sistemas?

Lo primero que vamos a hacer es definir cómo evolucionan este tipo de siste-
mas, pues las reglas que definimos en la sección 5 no funcionan. Sin embargo, una
ligera modificación de cómo se comportan las funciones de transición que hab́ıamos
estudiado anteriormente nos proporciona un marco para este tipo de sistemas.

Definición 8.1. Decimos que S = (F1, F2, . . . , Fn) es un sistema de FSMs en
comunicación sin orden en el caso de que las distintas FSMs generan outputs
en Σ⊕ (en vez de en Σ∗, como era habitual), es decir, δi : Qi × Σ? −→ Qi × (Σ⊕)

n

para 1 ≤ i ≤ n. Una configuración de S será una tupla de Q1 × Σ⊕ × Q2 × Σ⊕ ×
· · · ×Qn × Σ⊕.

La función de transición entre distintas configuraciones de S es δ : Q1 × Σ⊕ ×
Q2×Σ⊕×· · ·×Qn×Σ⊕ −→ Q1×Σ⊕×Q2×Σ⊕×· · ·×Qn×Σ⊕, que viene definida
de la siguiente manera:

contains(Bi, γ) ∧ δi(qi, γ) = (q′i, α1, α2, . . . , αn) =⇒
(q1, B1 + α1, . . . , qi−1, Bi−1 + αi−1, q

′
i, erase(Bi, γ) + αi, qi+1, Bi+1 + αi+1, . . . , qn, Bn + αn)

∈ δ(q1, B1, . . . , qi, Bi, . . . , qn, Bn)

En este caso contains(B, γ) es una función que dice si hay alguna ocurrencia del
literal γ ∈ Σ en el multiconjunto B (trivialmente cierto si γ = ε), erase(B, γ) es una
función que elimina una ocurrencia de γ de B (lo cual podŕıamos entender como
B \ {γ}), y + representa la suma usual de multiconjuntos (si un literal γ aparece a
veces en el multiconjunto A y b veces en B, entonces aparece a+ b veces en A+B).

35



Caṕıtulo 8 - Sistemas con buffers sin orden 36

Como hasta ahora, las configuraciones dependen de los estados en que están las
diferentes FSMs en cada instante, y los multiconjuntos se pueden interpretar como el
contenido de los buffers B1, B2, . . . , Bn, que esta vez funcionan como multiconjuntos.
La máquina Fi toma inputs de Bi y genera outputs que se añaden al resto de buffers.

Una vez vista la adaptación de la definición de sistemas de FSMs en comunicación
a esta situación, vamos a establecer una comparativa con las redes de Petri, pues son
los sistemas más conocidos que trabajan con multiconjuntos, es decir, con inputs y
outputs sin un orden definido.

8.1. Expresividad de los sistemas con buffers sin orden

Lo primero que vamos a hacer es comprobar que estos sistemas son en realidad
simulables por redes de Petri usuales. Vamos a recordar este concepto:

Definición 8.2. Una red de Petri N es una tupla (P, T,A,M,W ). P es el con-
junto de lugares de N , T el conjunto de transiciones y A ⊆ (P × T ) ∪ (T × P ) el
conjunto de arcos (o relación de flujo entre lugares y transiciones). En cada mo-
mento, cada lugar de P tiene una cantidad no negativa de tokens, indicada por el
marcaje M : P −→ N. Y cada transición de T puede consumir o generar una canti-
dad distinta de tokens en cada uno de los lugares que se relacionan con ella a través
de los arcos de A. La cantidad de tokens que se intercambian con cada transición
por medio de cada arco vienen determinados por W : A −→ N.

A la vista de la definición, veamos el resultado que augurábamos.

Proposición 8.3. Cualquier sistema de FSMs en comunicación con buffers sin
orden puede ser simulado por una red de Petri.

Demostración. Dado un sistema S = (F1, F2, . . . , Fn), vamos a construir una red
de Petri N que lo simule. La red de Petri será N = (P, T,A,M,W ), como en la
definición anterior. Supongamos que el alfabeto de S es Σ.

Por cada estado qi de cada máquina Fj tendremos un lugar en P , que denota-

remos qji . Estos lugares tendrán siempre a lo sumo un token, y representarán si la
máquina Fj está en el estado qi a lo largo de la simulación que hace N . Además,

por cada literal γ ∈ Σ y cada buffer Bj tendremos también un lugar, bjγ , que tendrá
tantos tokens como ocurrencias de γ haya en Bj en un instante determinado. En
principio, por las caracteŕısticas de los sistemas de FSMs, estos lugares no están
acotados.

Por cada transición de Fj , 1 ≤ j ≤ n, tendremos una transición en N . Es decir,
si numeramos las transiciones de cada máquina Fj desde el 1 hasta rj , el conjunto

de transiciones de N será T = {tji : 1 ≤ j ≤ n, 1 ≤ i ≤ rj}, donde tji simulará la
i-ésima entrada de δj .

Queda por tanto definir las relaciones entre lugares y transiciones, a través de re-
lación de flujo A. Supongamos que tenemos una transición arbitraria de δj , digamos



Caṕıtulo 8 - Sistemas con buffers sin orden 37

que la i-ésima, que funciona de la siguiente forma: δj(qk, α) = (qk′ , O1, O2, . . . , On),
donde Oa es el multiconjunto de literales que se mandan a Fa. Entonces la transición
tji simplemente tendrá que tomar un token de qjk para que la transición se tome desde

el estado qk de Fj , y de bjα para simbolizar que se está consumiendo el śımbolo α de
Bj (ambas con peso 1 en nuestra función W , pues solo se consumen un token cada

vez). Y tras esto pondrá un token en qjk′ para simbolizar el cambio de estado de Fj , y
en cada lugar baγ tantos tokens como veces aparezca el literal γ en Oa, simbolizando
que se env́ıan estos literales al buffer Ba de entrada de la máquina Fa. Esto vendrá
reflejado en nuestro caso por medio de pesos de los arcos de N : si γ aparece m veces
en Oa, entonces W (tji , b

a
γ) = m.

A modo de ejemplo de la construcción podŕıamos tener la siguiente situación.
Imaginemos un sistema con Σ = {α, β, γ}, y dos FSMs con 3 estados cada una. Solo
tendremos dos transiciones: δ1(q1, α) = (q2,∅, {β, γ, γ}), δ2(q3, γ) = (q1, {γ}, {β}).
La red de Petri que simula este sistema, según la construcción anterior, seŕıa (con
ciertos tokens puestos en distintos lugares a modo de ejemplo) la de la siguiente
figura (donde usamos el convenio usual para dibujar redes de Petri: ćırculos para
lugares y rectángulos para transiciones):

q1
1

q1
3

•

q1
2

b1α
• • •

b1β
•

b1γ

b2α
•

b2β
• •

b2γ
•

q2
3

•

q2
1

q2
2

t11 t32

F1

F2

Buffer 1

Buffer 2

1

1

1

2

1

1

1

1

1

1

Figura 8.1: Red de Petri que simulaŕıa el ejemplo explicado anteriormente según la
construcción que proponemos en esta proposición.



Caṕıtulo 8 - Sistemas con buffers sin orden 38

De esta forma es claro que la forma de actuar de N es la de una simulación com-
pleta de movimientos de S. Si además ponemos tokens inicialmente en los estados
iniciales de cada máquina de S, y en los buffers para que simbolicen el input, con-
seguimos que sus comportamientos sean el mismo, con lo que quedaŕıa demostrado
que podemos simular un sistema de FSMs mediante una red de Petri.

Hasta ahora hemos visto que las redes de Petri sirven para simular los sistemas
de FSMs en comunicación de una manera muy natural, pues basta tener un lugar
que guarde cada información presente en el sistema (estados de las FSMs y sus
buffers) y una transición de la red de Petri por cada transición de las FSMs. Pero lo
más interesante es que también se pueden simular redes de Petri con estos sistemas
de FSMs en comunicación, lo que nos arroja la conclusión de que están en el mismo
nivel en cuanto a expresividad se refiere. Vamos a hacer la demostración de este
hecho.

Proposición 8.4. Cualquier red de Petri puede ser simulada por un sistema de
FSMs en comunicación con buffers sin orden.

Demostración. Supongamos que tenemos una red de Petri N = (P, T,A,W ).
Los lugares serán P = {p1, p2, . . . , pn} y las transiciones T = {t1, t2, . . . , tm}. Veamos
cómo construir un sistema de FSMs en comunicación que la simule. En este caso, va
a ser más sencillo utilizar únicamente una FSM, por lo que tendremos un sistema
del tipo S = (F1). En realidad esta situación es la misma que si tuviéramos una
máquina más que devolviera todo lo que le llega sin modificarlo, como ya hicimos
en la demostración de la Turing completitud de los sistemas generales en 4.2. Por
tanto, realmente esta no es una situación nueva.

Consideraremos un alfabeto con n literales, tantos como lugares tenga N , diga-
mos Σ := {γ1, γ2, . . . , γn}. De esta forma, el número de literales γj que tenga nuestro
buffer se corresponderá con la cantidad de tokens que tendrá N en pj .

Tendremos además un estado inicial q0, y una serie de estados auxiliares de la
familia qj para simular cada una de las transiciones tj de N . Todo estado qj es-
tará conectado con q0 mediante una transición (qj ,∅) ∈ δ1(q0, ε). De hecho, si la
transición tj toma tokens de pi1 , pi2 , · · · , piN (donde posiblemente varios de estos
lugares estén repetidos, refiriéndose esto a que se toman varios tokens de un mismo
lugar según especifica W ) y deja tokens en pi′1 , pi′2 , . . . , pi′N′

(donde de nuevo posi-

blemente haya repetidos), usaremos N estados auxiliares para ir tomando en cada
movimiento un token, pues F1 está limitada a consumir un literal en cada una de
sus transiciones. Y al llegar al final, pondremos sin problema todos los tokens en
sus lugares correspondientes. Hay que tener en cuenta que el comportamiento de la
red de Petri no es secuencial como en este caso: no toma los tokens uno a uno para
ver si se activa una transición. Por tanto, hemos de tener cuidado con quedarnos
bloqueados en mitad de la simulación de una de estas transiciones porque falta uno
de los literales que comprobamos al final, por ejemplo. Para evitar esto, simplemen-
te construiremos transiciones que permitan deshacer estas acciones parciales que
hemos acometido, sin dejar por ello de simular la red de Petri N .



Caṕıtulo 8 - Sistemas con buffers sin orden 39

De manera más precisa, para simular la transición anterior tj , crearemos estados
auxiliares q1

j , q
2
j , . . . , q

N
j . Además, usaremos las siguientes transiciones para simular

cómo tj coge tokens: δ1(qj , γi1) = (q1
j ,∅), δ1(q1

j , γi2) = (q2
j ,∅), . . . , δ1(qN−1

j , γiN ) =

(qNj ,∅). Sin olvidarnos de las transiciones que nos permiten deshacer todos estos

pasos hechos individualmente: δ1(qj , ε) = (q0,∅), δ1(q1
j , ε) = (qj , {γi1}), δ1(q2

j , ε) =

(q1
j , {γi2}), . . . , δ1(qNj , ε) = (qN−1

j , {γiN }). Y una última transición para poner los

tokens donde corresponde: δ1(qNj , ε) = (q0, {γi′1 , γi′2 , . . . , γi′N′}).

Para que se entienda mejor se puede ver la figura 8.2:

q0 qj q1
j q2

j qN−1
j qNj

ε/∅ γi1/∅ γi2/∅ · · · γiN /∅

ε/{γi′1 , γi′2 , . . . , γi′N′}

ε/∅ ε/{γi1} ε/{γi2} · · · ε/{γiN }

Figura 8.2: Representación gráfica de la los diferentes estados y transiciones usados
en la simulación de la transición tj .

Con esta construcción podemos simular entonces la red de Petri N a través de
un sistema de FSMs, ya que hemos conseguido que las configuraciones del sistema
simulen los marcajes de N , con lo que la demostración habŕıa terminado.

A la vista de la demostración, comentaremos una contraparte de esta construc-
ción: al introducirse transiciones que lo que hacen es deshacer acciones ya acometi-
das, estamos haciendo que se generen una especie de livelocks en nuestro sistema de
FSMs, pues el sistema podŕıa avanzar en su ejecución sin realmente progresar.

8.2. Comparativa con otros tipos de redes de Petri

Existen multitud de variantes de las redes de Petri usuales que tienen diferentes
caracteŕısticas. Es interesante ver que, con ligeras modificaciones de nuestros siste-
mas de FSMs en comunicación, podemos conseguir dar cabida a algunas de estas
variantes. En este caso nos centraremos en dos tipos:

Definición 8.5. Las redes de Petri con arcos inhibidores (inhibitor arcs): son
redes de Petri usuales con un tipo adicional de arcos, denominados inhibidores. Se
añade a la red un conjunto I ⊆ P × T de forma que una transición t ∈ T solo se
puede tomar si no hay ningún token en cada lugar p de forma que (p, t) ∈ I.

Definición 8.6. Las redes de Petri con arcos restablecedores (reset arcs): de
nuevo son redes de Petri usuales con un tipo adicional de arcos. Estas redes tendrán



Caṕıtulo 8 - Sistemas con buffers sin orden 40

un conjunto R ⊆ P×T de forma que después de que se ejecute una transición t ∈ T ,
se quitan todos los tokens que haya en los lugares p de forma que (p, t) ∈ R.

Vistos estos nuevos modelos de redes de Petri, veamos qué modificaciones pode-
mos introducir en nuestros sistemas de FSMs para que se asemejen a ellos. Haremos
en este caso un análisis no tan exhaustivo de las construcciones para poder centrar-
nos realmente en cómo vaŕıan las propiedades de los distintos tipos de sistemas de
FSMs dependiendo de sus definiciones.

Para poder definir correctamente las transiciones en estos sistemas con buffers
sin orden, hasta ahora hemos hecho uso de una función contains(B, γ) que, dados
un multiconjunto B y un literal γ, nos dice si hay alguna ocurrencia de γ en B,
vamos a considerar un nuevo tipo de transición en nuestras FSMs. Dado un alfabeto
Σ, definimos Σ := {γ : γ ∈ Σ}. Estos nuevos literales significarán lo siguiente: si
tenemos una transición δi(qi, γ) = (q′i, A) en la FSM Fi de un sistema de FSMs en
comunicación (ahora δi : Qi ×

(
Σ? ∪ Σ

)
−→ Qi × (Σ⊕)n), esto significará que la

transición se toma si en el buffer Bi no hay ningún literal γ, y se transitaŕıa de q a
q′ produciendo A como output. Es decir, con las notaciones del apartado anterior:

¬contains(Bi, γ) ∧ δi(qi, γ) = (q′i, α1, α2, . . . , αn) =⇒
(q1, B1 ∪ α1, . . . , qi−1, Bi−1 ∪ αi−1, q

′
i, Bi ∪ αi, qi+1, Bi+1 ∪ αi+1, . . . , qn, Bn ∪ αn)

∈ δ(q1, B1, . . . , qi, Bi, . . . , qn, Bn)

Con este nuevo alfabeto y sus nuevas transiciones asociadas es claro que podemos
introducir arcos inhibidores de la misma manera en la que introdućıamos flechas
usuales en el apartado anterior a la hora de simular una red de Petri. Por tanto,
cualquier red de Petri con arcos inhibidores puede ser simulada por este tipo de
sistemas de FSMs en comunicación. Y el rećıproco también es trivialmente cierto,
la misma construcción anterior serviŕıa asimismo.

Esto es interesante por las propiedades que adquieren los sistemas de FSMs
con esta pequeña modificación de comportamiento. Por ejemplo, en el caso de las
redes de Petri (y por tanto en nuestros sistemas de FSMs en comunicación sin
orden, según hemos definido en la definición 8.1) es bien conocido que el problema
de recubrimiento (coverability o control state reachability en inglés, el problema de
saber si se puede alcanzar un marcaje mayor que uno prefijado, que es el que más se
asemeja al de la alcanzabilidad en sistemas de FSMs) es decidible. Pero pasa a ser
indecidible en cuanto usemos transiciones con literales del tipo γ, pues en redes de
Petri con arcos inhibidores el problema no es decidible (como podemos ver en [12],
teorema 3.2.21).

Al ser los sistemas con arcos inhibidores Turing completos ([3], teorema 3), seŕıa
posible simular también arcos restablecedores mediante los sistemas de FSMs en co-
municación que acabamos de definir. Básicamente habŕıa que añadir ciertos estados
en los que las FSMs quedaŕıan en bucle vaciando de un tipo de literal sus buffers de
lectura, utilizando para terminar dicho bucle los literales γ, que señalizarán que ya
se ha vaciado el buffer de dicho literal.



Caṕıtulo 8 - Sistemas con buffers sin orden 41

Pero esto no resulta tan interesante como definir una modificación de los siste-
mas que tenga exactamente la misma expresividad que las redes de Petri con arcos
restablecedores, en un estadio anterior a la Turing completitud. Esto lo podemos
comprobar, por ejemplo, porque en redes de Petri con arcos restablecedores el pro-
blema de la terminación es decidible [11], mientras que en las máquinas de Turing
no lo es (es el Problema de Parada, resuelto por Turing).

Definamos por tanto otro tipo de sistemas de FSMs, de la siguiente forma. Dado
un sistema usual S de FSMs en comunicación en el que los buffers no tienen orden,
con alfabeto Σ, llamaremos Σ̂ := {γ̂ : γ ∈ Σ}. Estos nuevos literales servirán
para simular los arcos restablecedores, de forma que al tomarse una transición con
γ̂, se eliminan todos los literales γ del buffer en cuestión. Más formalmente, las
transiciones asociadas a estos nuevos literales son:

δi(qi, γ̂) = (q′i, α1, α2, . . . , αn) =⇒
(q1, B1 + α1, . . . , qi−1, Bi−1 + αi−1, q

′
i, erase all(Bi, γ) + αi, qi+1, Bi+1 + αi+1, . . . , qn, Bn + αn)

∈ δ(q1, B1, . . . , qi, Bi, . . . , qn, Bn)

donde erase all(B, γ) es una función sobre multiconjuntos que elimina todas las
ocurrencias del literal γ en B.

Notamos que básicamente la interpretación de estas transiciones es que, tras
tomar la transición, vaćıan el buffer del literal γ. Además, se toma la transición con
literal γ̂ sin necesidad de que haya literales γ en el buffer, como sugiere la definición
de arcos restablecedores (no obstante esto se podŕıa cambiar fácilmente). Por ello, es
claro que usando la construcción descrita en la proposición 8.4 servirá para simular
redes de Petri con arcos restablecedores si usamos FSMs de este nuevo tipo que
hemos construido. Y es fácil darse cuenta de que el rećıproco es también cierto: si
introducimos arcos restablecedores en la construcción de la proposición 8.3, podemos
simular cualquiera de estos nuevos sistemas de FSMs en comunicación.

En este caso resulta de nuevo interesante la variación en cuanto a propiedades
que experimentan los sistemas de FSMs con esta modificación, que podŕıa en princi-
pio no parecer muy grande. En este caso, el problema de recubrimiento sigue siendo
decidible (porque lo es para redes de Petri con arcos restablecedores, como pode-
mos ver en el caṕıtulo 4 de [11]), pero el problema de la alcanzabilidad (llegar a un
marcaje concreto en vez de a un marcaje mayor que uno concreto) se convierte en
indecidible (pues lo es para las redes de Petri con arcos restablecedores, como pode-
mos comprobar en [4]), al igual que cuando introdućıamos arcos inhibidores. Esto
nos indica que realmente los problemas interesantes relacionados con las configura-
ciones alcanzables están en este caso realmente en el borde entre lo decidible y lo no
decidible. Al final estos resultados se apoyan en una noción relacionada, la denomi-
nada backwards reachability, que śı continúa siendo decidible ([12], 3.2.20) cuando
hay arcos restablecedores, y marca realmente la diferencia con la introducción de
arcos inhibidores.

En cuanto a complejidad de estos problemas de decisión, resulta que todos ellos
son EXSPACE-duros. Esto en realidad es consecuencia de que los problemas de
decisión más usuales (como el de la alcanzabilidad que hemos comentado, la ter-
minación, la acotación...) en redes de Petri usuales lo son, y además hay una cota



Caṕıtulo 8 - Sistemas con buffers sin orden 42

inferior de 2O(
√
n) en el espacio que requieren para ser resueltos (como se puede ver,

por ejemplo, en [12], pág. 57). Esto nos dice bastante sobre la dificultad que tiene
en el caso general resolver estos problemas.



Caṕıtulo 9

Sistemas de Mensajes Perdidos

En nuestro camino explorando diferentes versiones de nuestros sistemas de FSMs
podemos visitar uno de los modelos más conocidos y estudiados de este tipo. Si
suponemos que los canales de comunicación que usamos (los buffers que ayudan a la
comunicación en nuestro caso) no son ideales y, por tanto, son susceptibles a fallos
de forma que algunos literales puedan desaparecer de ellos en cualquier momento
sin ningún mecanismo que controle estas pérdidas, llegamos a un concepto bastante
similar al de los Sistemas de Mensajes Perdidos (LCS por su nombre en inglés: Lossy
Channel Systems).

Los LCS usuales que podemos encontrar en la literatura son un tipo de sistemas
de FSMs en comunicación en los cuales hay un tipo de transición adicional: en
cualquier punto de la ejecución, pueden desaparecer un conjunto de literales de
cualquier buffer del sistema. Este comportamiento es puramente no determinista: no
hay manera de controlarlo, puede surgir en cualquier momento y afectar a cualquier
grupo de literales. Dado este no determinismo inherente a los LCS, en general se
suele permitir también que las FSMs utilizadas sean no deterministas (y recordemos
que no toda FSM no determinista se puede convertir en una determinista, pues
ante una misma secuencia de inputs las FSMs no deterministas pueden generar
potencialmente más cadenas de outputs diferentes que las deterministas), lo cual los
diferencia un poco más de nuestros sistemas de FSMs.

En general, un LCS puede, en cierto sentido, simular las ejecuciones de un siste-
ma de FSMs, pues una de sus posibles ejecuciones es aquella en la que las transiciones
que pierden literales nunca se activan, y en concreto este seŕıa el comportamiento
que tienen nuestros sistemas. No obstante, las propiedades de ambos tipos de sis-
temas no son las mismas porque en los LCS hay muchas más posibles ejecuciones
en las que se pierden algunos literales de los buffers. En cambio, una simulación en
sentido contrario no es posible a menos que introduzcamos cambios en la definición
de nuestros sistemas (no es posible simular esas pérdidas de literales no determinis-
tas con nuestros sistemas de FSMs usuales), pues hay propiedades en las que ambos
modelos difieren: por ejemplo, el problema de la terminación (que el sistema no
tenga ramas de ejecución infinitas dado un input) es decidible en el caso de los LCS
e indecidible en el de los sistemas de FSMs en comunicación (Problema de Parada).

Una forma de hacer que nuestros sistemas de FSMs pudieran tener la capaci-
dad de perder mensajes de forma no determinista, como ocurre en los LCS, seŕıa
introducir un cierto grado de no determinismo en las FSMs. Por ejemplo, si para
cada transición δ(q, α) = (q′, β) de una de las FSMs de nuestro sistema permiti-
mos añadir también la transición δ(q, α) = (q′, ε), estaŕıamos pudiendo simular este

43



Caṕıtulo 9 - Sistemas de Mensajes Perdidos 44

fenómeno ya que, de manera no determinista, podŕıan no llegar los mensajes a su
buffer destino. Además, esto es introducir un no determinismo muy controlado, aśı
que tampoco es que el cambio haya sido excesivo. Lo interesante va a ser la diferencia
entre propiedades que generan estos cambios.

Aunque pueda parecer algo paradójico, numerosos problemas de decisión son
más tratables en los LCS que en el caso de los sistemas de FSMs en comunicación y
las máquinas de Turing, donde esencialmente los problemas son indecidibles en su
mayoŕıa. En concreto, un problema de vital importancia, como es el de la alcanzabi-
lidad, es decidible para los LCS ([2], caṕıtulo 5) . También es decidible el problema
de la inevitabilidad (dado un conjunto de estados, ¿es inevitable que cualquier eje-
cución maximal pase por alguno de dichos estados?), que engloba el problema de
la terminación (usando como conjunto de estados aquellos estados en los cuales la
ejecución termina), muy importante también en la teoŕıa de autómatas ([21], teo-
rema 8). También son decidibles otras propiedades que comprueban que a lo largo
de las ejecuciones maximales se conservan ciertas propiedades, lo cual es de utilidad
en este caso debido a que es importante tener ciertos métodos de verificación del
funcionamiento de los sistemas que palien en cierto modo su naturaleza, que permite
que los mensajes se pierdan.

No obstante, ni mucho menos todas las propiedades de estos sistemas son de-
cidibles: en general, otras como la acotación (¿la cantidad de literales que puede
haber en un canal/buffer a lo largo de cualquier ejecución está acotada?) o ciertas
propiedades de justicia, como saber si es inevitable pasar por un cierto estado de
control infinitas veces, son indecidibles ([1], teorema 3.7).

Más aún: a pesar de ser decidibles los problemas antes comentados, como el de la
alcanzabilidad, tienen una complejidad extremadamente grande. No están asociados
a funciones recursivas primitivas ([27], teoremas 4.2, 4.4). De hecho, se puede ver la
gran distancia a la que están de esta clase de funciones con un breve vistazo a la
Jerarqúıa de Crecimiento Rápido (Fast Growing Hierarchy): las funciones recursivas
primitivas están asociadas a ordinales acotados superiormente por ω (el primer or-
dinal numerable), mientras que los problemas de la alcanzabilidad e inevitabilidad
están asociados al ordinal ωω.

9.1. Introduciendo justicia en las ejecuciones

Una vez vistas las propiedades básicas de los LCS en general, vamos a comprobar
que introducir a nuestros sistemas de FSMs la capacidad de hacer que los mensajes se
puedan perder de forma no determinista hace que consigamos una clase restringida
de los LCS generales, y esto nos va a proporcionar alguna ventaja interesante.

Por ejemplo, seŕıa interesante introducir ciertas nociones de justicia en este tipo
de sistemas. Esto se debe a que el hecho de que los mensajes se puedan perder puede
llegar a degradar bastante la comunicación entre varias máquinas en una situación
real, en la cual podŕıa ser que la red fallara mucho y casi ningún mensaje se mandara.
Si tuviéramos asegurada cierta justicia en nuestro ambiente, como que ciertos com-
portamientos se tienen que dar periódicamente sean cuales sean las circunstancias,



Caṕıtulo 9 - Sistemas de Mensajes Perdidos 45

podŕıamos al menos intentar paliar los posibles fallos de la red repitiendo el env́ıo
de los mensajes, pues la justicia nos aseguraŕıa que, tarde o temprano, es seguro que
los mensajes llegarán.

Dos modelos de justicia interesantes que van a ser de especial interés son los que
se estudian en [20]. Para un sistema S = (F1, . . . , Fn):

Decimos que una ejecución es débilmente justa si para cada máquina Fi se
cumple que está bloqueada (es decir, que dada la composición de su buffer
y su estado actual, no puede avanzar en ese instante) un número infinito de
veces a lo largo de la ejecución o que infinitos pasos de la ejecución de S son
pasos de Fi en los que desaparecen literales de su buffer.

Decimos que una ejecución es fuertemente justa si para cada máquina Fi se
cumple que a partir de un cierto paso de la ejecución de S Fi está siempre
bloqueada o si infinitos pasos de la ejecución de S son pasos de Fi en los que
desaparecen literales de su buffer.

Ambos conceptos básicamente de lo que nos están informando es de que, mientras
no están bloqueadas, las máquinas van alternándose relativamente entre ellas en su
ejecución, hay una cierta justicia entre todas las máquinas. En la justicia fuerte
además se exige que cada máquina no se bloquee casi nunca o que termine en
tiempo finito su ejecución, lo cual da la idea de que, entre aquellas máquinas que
no se bloqueen en tiempo finito, tendrá que haber gran grado de alternancia en las
ejecuciones. Además, lógicamente, si una ejecución es fuertemente justa, también es
débilmente justa.

Veamos ahora qué pasa si imponemos estos sentidos de justicia a la modificación
de los sistemas de FSMs en comunicación en los cuales permitimos que se pierdan
mensajes. Estudiaremos qué pasa con el problema de la terminación imponiendo
estos conceptos de justicia: ¿todas las ramas de ejecución de nuestro sistema acaban
en tiempo finito imponiendo justicia fuerte/débil? La respuesta es la contraria a ¿hay
alguna ejecución infinita en la que se respete la justicia fuerte/débil?, que también
puede servir en ocasiones para diferentes interpretaciones.

F1

F2

· · ·

Fn

Buffer 1

Buffer 2

· · ·

Buffer n

Figura 9.1: Esquema de las comunicaciones en un
sistema de FSMs en comunicación.

Lo que podemos ver es que,
por la forma en que hemos
diseñado nuestros sistemas de
FSMs, cada buffer solo sirve co-
mo input de una única máqui-
na (lo cual podemos ver gráfi-
camente en la figura 9.1). Es-
to hace que tengamos una clase
restringida de los LCS, que en
[20] llaman sistemas sin canales
multiplexados.

Esto es interesante porque
en LCS generales se tiene el si-
guiente resultado:



Caṕıtulo 9 - Sistemas de Mensajes Perdidos 46

Proposición 9.1 (3.1 en [20]). En LCS sin canales multiplexados el problema de
la terminación imponiendo justicia fuerte/débil es decidible.

Por tanto, en el caso de nuestros sistemas de FSMs modificados, como acabamos
de ver en los párrafos anteriores, están contenidos en la subclase de los LCS sin
canales multiplexados, podemos aplicarles el teorema 9.1 (sabiendo que, como es
sencillo comprobar, ser decidible es una propiedad que las subclases heredan). Esto
nos conduce al siguiente resultado:

Corolario 9.2. En los sistemas de FSMs en comunicación modificados para que se
puedan perder mensajes de los buffers de manera no determinista, el problema de la
terminación es decidible si imponemos justicia fuerte o débil.

Esta propiedad es interesante porque nos informa de que podemos introducir
conceptos de justicia a bajo coste (sin perder la decibilidad de la propiedad de
terminación). Y es interesante introducir la justicia porque aśı tenemos algunas
certezas más que en el caso de que no tengamos absolutamente ningún control sobre
la pérdida de mensajes en nuestro sistema.



Caṕıtulo 10

Complejidad de algunas
propiedades

A pesar de que, en virtud del teorema de Rice, todos los problemas de decisión
no triviales sobre sistemas de FSMs en comunicación son indecidibles (pues lo son
para las máquinas de Turing), podemos estudiar la complejidad de resolver alguno
de estos problemas en algunas de sus versiones simplificadas que śı queden en el
rango de lo decidible.

10.1. El problema de la alcanzabilidad finita

En este apartado vamos a entrar más a fondo en una de las propiedades básicas: la
alcanzabilidad. Como el problema de la alcanzabilidad, en su versión general, resulta
indecidible, en este caso estudiaremos la alcanzabilidad finita (que aqúı denotaremos
también N -alcanzabilidad, para que quede claro que la limitación de la finitud viene
prefijada por una constante N), que es el siguiente problema: dado un natural N
y una posible configuración de nuestro sistema de FSMs en comunicación S, ¿es
posible alcanzar dicha configuración dando S a lo sumo N pasos en su ejecución?
De hecho, veremos el caso de que la configuración que buscamos alcanzar sea una
cualquiera en la que S acepta, planteándonos el problema ¿puede aceptar S en a lo
sumo N pasos en su ejecución? Veremos que este problema de decisión no es sencillo
de resolver en el caso general, tanto que resulta ser un problema NP-completo.
Vamos a proceder a la demostración de este hecho.

Lema 10.1. El problema de la alcanzabilidad finita en sistemas de FSMs en comu-
nicación es NP.

Demostración. Si tenemos un sistema de FSMs en comunicación S = (F1, F2, . . . , Fn),
saber si S alcanzará un determinado estado en menos de N pasos es un problema
NP: de manera no determinista se puede, en caso de que haya forma de alcanzar
dicho estado, acertar cuál es el orden de ejecución, es decir, si el siguiente paso del
sistema será ejecutar una transición de F1, de F2 . . . o de Fn. Dado este orden de
ejecución, es ya trivial comprobar que funciona: simplemente vamos ejecutando las
transiciones en F1, F2, . . . , Fn y modificando los buffers correspondientes, y al final
comprobamos si el estado al que hemos llegado es el esperado. Esta comprobación
es claramente polinómica, de hecho O(N) si implementamos convenientemente las
operaciones de inserción y extracción de elementos de los buffers.

47



Caṕıtulo 10 - Complejidad de algunas propiedades 48

Hay que tener en cuenta que para que esto sea realmente un comportamiento
polinómico, N tiene que haber sido recibido como input en base unaria, es decir, el
input N se representa recibiendo N tokens del mismo tipo. Notemos que es impor-
tante porque si nos dieran N como input en binario, por ejemplo, O(N) seŕıa un
tiempo exponencial en el tamaño del input. Pero es una hipótesis razonable trabajar
en base unaria en este tipo de situaciones porque si no, incluso el simple problema de
que un autómata dé N pasos tarda un tiempo exponencial en ejecutarse; mientras
que considerando la base unaria, es como si nuestro autómata fuera consumiendo
tokens con cada paso que da y el comportamiento seŕıa polinómico, lo cual resulta
bastante más razonable.

Ahora querŕıamos demostrar laNP-completitud del problema de laN -alcanzabilidad
en estos sistemas: para ello, vamos a reducir el problema del 3-SAT (del cual es bien
conocida su NP-completitud) al de la N -alcanzabilidad de uno de estos sistemas.
Describamos esta reducción en detalle.

Teorema 10.2. El problema de la alcanzabilidad finita en sistemas de FSMs en
comunicación es NP-completo.

Demostración. Supongamos que tenemos como input una fórmula de 3-SAT φ
con n variables, y queremos decidir si φ es o no satisfactible (es decir, resolver el
problema del 3-SAT) usando un sistema de FSMs.

Vamos a crear un sistema S de FSMs en comunicación con varias máquinas
(donde no todas las máquinas se comunicarán con todas las restantes). Dos de ellas
serán F1, F2: F1 tiene un único estado en el cual devuelve 0 ante cualquier input (y
permanece en ese estado); mientras que F2 tiene, de nuevo, un único estado (donde
siempre permanece) en el cual devuelve esta vez un 1 ante cualquier input. De
esta forma, fruto del no determinismo de las comunicaciones de F1, F2, podŕıamos
generar cualquier cadena compuesta por ceros y unos, lo cual vamos a utilizar con
más máquinas. Los outputs tanto de F1 como de F2 irán únicamente a la máquina
F3, que posteriormente definiremos.

q1
0 ε/0

Figura 10.1: Esquema gráfico de F1.

q2
0 ε/1

Figura 10.2: Esquema gráfico de F2.

Usaremos también un checker de fórmulas de 3-SAT , que funcionará de la si-
guiente forma: como la fórmula φ, que este checker recibirá como input, tiene n
variables (que podemos suponer ordenadas de algún modo), el checker usará los
n primeros inputs que le lleguen (en este caso de F1 y F2, como veremos) para
asignárselos como valores de las variables de φ, en ese mismo orden. Una vez le
lleguen esos primeros n inputs, podrá comprobar si esos valores satisfacen φ, y gene-
rar una respuesta afirmativa o negativa. Este checker se puede construir de manera
sencilla como máquina de Turing. Y como vimos en el apartado 4.2, los sistemas
de FSMs en comunicación con 2 FSMs son una clase Turing completa, aśı que este
checker puede ser implementado mediante 2 FSMs en comunicación, digamos F4, F5.

Además, el checker puede ser implementado sencillamente de forma que se ejecute



Caṕıtulo 10 - Complejidad de algunas propiedades 49

en tiempo lineal con respecto a los inputs de las fórmulas que recibe. Y, como
vimos en el apartado 4.2, la transformación de máquinas de Turing a sistemas de
FSMs en comunicación era suficientemente buena como para poder afirmar que
solo añad́ıamos una cantidad polinómica de sobrecoste. Por tanto, podemos afirmar
que el comportamiento del checker implementado con F4, F5 será polinómico en el
número de literales de la fórmula φ que nos den como input.

Para comunicar las máquinas F1, F2 con este checker (F4, F5), usaremos una
sencilla máquina F3 intermediaria: recibirá los outputs que F1 y F2 generen, y los
dejará pasar (en un único canal), únicamente, hacia el checker, en el orden que le
lleguen. De esta forma conseguimos simplificar la forma en que llegan los ceros y
unos generados por F1, F2 al checker.

q3
0

0/0

1/1

Figura 10.3: Esquema gráfico de F3.

Y por último tenemos una máquina F6 que lo único que hace es esperar la
respuesta del checker. Cuando F4 y F5 hayan procesado suficiente información como
para saber si la fórmula φ es o no satisfactible, enviarán un mensaje (afirmativo o
negativo en cada caso, digamos que mediante los literales >,⊥) a F6. La recepción
de un mensaje afirmativo hará que F6 transite a un estado diferente q6

f , que será
el único estado de aceptación de S, o sea, que las únicas configuraciones de S de
aceptación son aquellas en las que F6 está en q6

f (reduciendo aśı el problema a una
especie de alcanzabilidad finita de F6 dentro del sistema S). Y el problema de la
N -alcanzabilidad de S en este caso lo plantearemos en este caso, como explicábamos
al inicio, como ¿alcanza S su configuración de aceptación en menos de N pasos de
S?

q6
0 q6

f

>/ε

x/ε (x 6= >)

Figura 10.4: Esquema gráfico de F6.

Con esto ya tendŕıamos nuestro sistema S = (F1, F2, F3, F4, F5, F6) construido,
de forma que las diferentes máquinas se comunican únicamente con las que muestra el
diagrama de la figura 10.5. Veamos ahora por qué funciona realmente esta reducción.



Caṕıtulo 10 - Complejidad de algunas propiedades 50

F1

F2

F3
checker

(F4 + F5)

input (φ)

F6

Figura 10.5: Diagrama explicativo de las comunicaciones que se establecen en S.

Dada la construcción anterior, al checker le llegarán ceros o unos en función de
qué máquina ejecute el siguiente paso de entre F1, F2. Supongamos que el checker
formado por F4, F5 tiene que ejecutar p(|φ|) pasos para poder decidir si la fórmula
φ (denotamos por |φ| el tamaño de la fórmula φ como input, y recordamos que tiene
n ≤ |φ| variables) es o no satisfactible. Por la discusión anterior, p es un polinomio.

Entonces, en caso de que φ sea satisfactible, definiendo N := p(|φ|) + 2n + 1 ≤
p(|φ|)+2|φ|+1, es claro que en N pasos S podrá llegar a su estado de aceptación, es
decir, aquel en el que F6 está en q6

f (p(|φ|) pasos serán del checker, n de las máquinas
F1, F2 para generar los literales que hacen φ cierta, n de F3 para dejar pasar estos
literales por un mismo canal y 1 final de la respuesta que el checker env́ıa a F6).

Y, ciertamente, el rećıproco también es cierto: si la fórmula φ no es satisfactible,
en ninguna ejecución de S de longitud N el sistema podrá llegar a su estado de
aceptación. Por tanto, podemos concluir que la reducción del problema de la satis-
factibilidad de φ, una fórmula cualquier de 3-SAT , ha sido reducida a un problema
de N -alcanzabilidad en sistemas de FSMs en comunicación.

Además, la reducción es polinómica porque la construcción de S es polinómi-
ca respecto al tamaño de φ (pues la construcción de cada máquina es en verdad
independiente de φ, aśı que podemos considerar que la construcción de S es O(1)
en cuanto a número de estados, y lineal en cuanto a tamaño de los buffers, pues el
checker recibe el input completo y ninguna máquina más tiene literales en su buffer
inicialmente), y N también lo es.

De esta forma, estamos ya en posición de afirmar que el problema de la N -
alcanzabilidad en sistemas de FSMs es en efecto NP-completo, como queŕıamos
demostrar.

De hecho, que el problema sea NP-completo no debeŕıa resultarnos una gran
sorpresa en realidad, pues el alt́ısimo grado de no determinismo que tienen los sis-
temas de FSMs en sus comunicaciones hace prácticamente imposible conseguir que
pasen a la frontera de lo polinómico. De hecho, incluso con únicamente 2 máquinas,
como haćıamos en la demostración anterior con F1 y F2, el intercalado que puede
existir entre sus ejecuciones hace que el número de posibles cadenas de ceros y unos
que le puedan llegar a la F3 anterior crezca exponencialmente conforme a los pasos



Caṕıtulo 10 - Complejidad de algunas propiedades 51

que ejecutan F1 y F2.

Si dejamos que a F3 le lleguen n literales, habrá 2n cadenas posibles que le
puedan llegar, un crecimiento claramente exponencial. Pero resulta más interesante
comprobar que aunque limitemos la capacidad de intercalado de F1 y F2, vuelven a
generarse una cantidad exponencial de cadenas. Esto lo podemos comprobar impo-
niendo unas ciertas condiciones de justicia en estas comunicaciones.

Por ejemplo, si no dejamos que una máquina ejecute más de k(≥ 2) pasos
seguidos, podŕıamos esperar que disminuyera bastante el número de cadenas po-
sibles que se pueden generar. Pero resulta que sigue siendo exponencial, pues la
cantidad de cadenas de longitud n que se podrán generar cumple la recurrencia
cn = cn−1 + cn−2 + . . .+ cn−k, una de las llamadas sucesiones de Fibonacci generali-
zadas, que tienen carácter exponencial, con bases comprendidas entre ϕ ≈ 1,6180 . . .
y 2 ([28], lema 3.6). Si limitamos que las 2 máquinas no puedan ejecutar k pasos
consecutivos, obtenemos un resultado similar.

El caso más fuerte en este sentido seŕıa uno en el cual implementáramos una
justicia tal que solo permitiéramos ejecuciones intercaladas de F1 y F2, de forma
que, de alguna forma, pudiéramos dividir cada cadena recibida por F3 en grupos
de dos literales que podŕıan ser únicamente 01 o 10. Igualmente, en este caso cn ≈
2n/2 =

√
2
n
, que seguiŕıa siendo exponencial.

De esta forma vemos que, aún limitando artificialmente la capacidad de comuni-
cación de las distintas máquinas mediante diferentes tipos de justicia, continuamos
obteniendo cantidades no polinómicas de posibles ejecuciones, lo cual nos indica que
pod́ıamos esperar el resultado que hemos dado en este caṕıtulo.

10.1.1. En sistemas con buffers acotados

A modo de comparativa podemos considerar el problema de la alcanzabilidad
finita en el caso de sistemas de FSMs en comunicación con buffers acotados, tal
y como definimos en el apartado 5.1. En este caso, y en el mismo esṕıritu que
obteńıamos que su expresividad era bastante limitada, pues son tan expresivos como
los autómatas finitos (como vimos en 7.1), vamos a conseguir ver que el problema
de la N -alcanzabilidad es mucho más sencillo de resolver, pues es polinómico en N .

Lema 10.3. El problema de la alcanzabilidad finita en sistemas de FSMs en comu-
nicación con buffers acotados es polinómico (P).

Demostración. Dado un sistema S de FSMs en comunicación con buffers acota-
dos, podemos conseguir un autómata finito F equivalente, cuyo tamaño no depende
de N y es polinómico en el tamaño de S, como vimos al final del caṕıtulo 7. Y la
construcción del grafo de alcanzabilidad de F hasta llegar a profundidad N (pues
más allá no vamos a obtener respuestas al problema de la N -alcanzabilidad, aśı que
no lo necesitamos) es O(N): en efecto, a cualquier profundidad d, F solo podrá
estar en una cantidad O(1) de estados, pues son los que resultan de considerar los
estados de F (constantes respecto a N por la discusión anterior); y para construir el
siguiente nivel del grafo (profundidad d+ 1) necesitamos solo considerar los estados



Caṕıtulo 10 - Complejidad de algunas propiedades 52

del nivel d. Por tanto, cada nivel se crea en tiempo constante, y de ah́ı resulta que
llegar hasta el nivel N es O(N).

Al ser la reducción del problema del problema de la N -alcanzabilidad en S al
de la N -alcanzabilidad en F polinómica en el tamaño de S, y ser también grafo de
alcanzabilidad de F de tamaño polinómico en N , es claro que el problema de la
N -alcanzabilidad se puede resolver en tiempo polinómico respecto al tamaño de los
datos del problema.

Como vemos, esto establece de nuevo una gran diferencia entre la complejidad
de los sistemas de FSMs en comunicación generales y los que tienen la limitación de
tener los buffers acotados.

10.2. El problema de regreso al estado inicial

Analizamos ahora otro problema de decisión interesante en el caso de los sistemas
de máquinas de estados o, en general, de distintos tipos de autómatas: el problema
de saber si desde cualquier configuración alcanzable se puede regresar a la configu-
ración inicial. De nuevo, este problema resulta en su versión general indecidible para
nuestros sistemas fruto del Teorema de Rice, pero podemos crear versiones finitis-
tas que sean decidibles e interesantes al mismo tiempo. En este caso la pregunta
será: para cualquier secuencia de M pasos de nuestro sistema, ¿existe un camino de
longitud k, con k ≤ N , de forma que tras esos M + k pasos el sistema vuelva a su
configuración inicial? Consideraremos M y N prefijados, como datos del problema.

Este problema se puede expresar de forma lógica como (a modo de pseudocódigo):

∀ paso1, paso2, . . . , pasoM ∃ paso′1, paso′2, . . . , paso′k
es igual(inicial, aplicar(inicial, [paso1, . . . , pasoM , paso

′
1, . . . , paso

′
k]))

Como podemos aplicar acciones sobre nuestros sistemas en tiempo polinómico y
la cantidad de pasos es también polinómica en M y N , es claro que este problema
es del tipo ∀P∃PP , es decir, que pertenece a la clase de complejidad ΠP

2 .

Lo interesante va a ser comprobar que de hecho este problema es completo den-
tro de esta clase, lo cual nos da la idea de que es en realidad dif́ıcil de resolver. Para
ello, vamos a reducir un problema del tipo del de SAT a nuestro problema. En con-
creto, será el problema QSAT2 (también llamado QBF2), que trata de determinar si
una fórmula de SAT con ciertos cuantificadores sobre variables (en este caso prime-
ro ciertos cuantificadores universales y después otros existenciales, necesariamente
en ese orden) es satisfactible. Y es bien sabido que este problema es Πp

2-completo
(al igual que sus análogos QSATk en Πp

k), pues de hecho son los problemas más
protot́ıpicos con esta propiedad.

La idea para la simulación de este problema es construir un sistema de FSMs
en comunicación que simule exactamente lo que esperamos en el problema QSAT2:
habrá una primera fase en la que asignaremos cualquier valor a ciertas variables de
nuestra fórmula (y para conseguir potencialmente cualquier asignación, usaremos el



Caṕıtulo 10 - Complejidad de algunas propiedades 53

no determinismo de las comunicaciones entre las máquinas) y después habrá otra fase
donde el resto de las variables intentarán tomar valores que satisfagan la fórmula de
SAT (para lo cual también utilizaremos el no determinismo de las comunicaciones
entre máquinas). Tras estas asignaciones, comprobaremos si la fórmula se satisface,
y solo en ese caso mandaremos ciertos mensajes a cada máquina para que vuelva a
su estado inicial, y que por tanto el sistema en conjunto vuelva a la configuración
inicial.

Vemos que, aunque las ideas son similares a las que usábamos en el caso de la
alcanzabilidad finita (usar el no determinismo de las comunicaciones para generar
una cantidad exponencial de caminos y después mezclarlo con otros comportamien-
tos deterministas que nos permitan comprobar las propiedades requeridas), el hecho
de tener que distinguir muy claramente la parte en que simulamos los cuantificado-
res universales y existenciales va a hacer que la construcción se complique un poco
respecto a la de la alcanzabilidad finita, pues debemos tener cuidado con que varias
máquinas han de estar bloqueadas en ciertos momentos para no mezclar las dos fases
de la simulación. No obstante, la idea principal sigue siendo aprovechar y controlar
el no determinismo de las comunicaciones entre máquinas.

Teorema 10.4. La versión finitista del problema de regreso a la configuración inicial
en sistemas de FSMs en comunicación es ΠP

2 -completo.

Demostración. Supongamos que tenemos como input una fórmula ϕ de SAT , con
m + n variables que denotaremos X1, . . . , Xm+n. Ahora queremos resolver el pro-
blema de QSAT2: ¿para cualquier asignación de valores de verdad a las m primeras
variables (porque sin pérdida de generalidad podemos suponer que están nombradas
para que sean las primeras) existe una asignación de valores de las otras n variables
que satisfaga ϕ?

Vamos a construir un sistema S muy similar al de que ya usamos en la demos-
tración del teorema 10.2, aunque va a tener dos partes bien diferenciadas que nos
van a ayudar a distinguir entre las dos partes que tiene el problema que queremos
resolver. Tendremos 9 FSMs: dos generadores de ceros (F1, F4), dos generadores de
unos (F2, F5), dos máquinas que intercalan los ceros y unos de los generadores an-
teriores (F3, F6), dos máquinas que simularán un checker de SAT (F7 y F8) y una
máquina que se encargará de restablecer la configuración inicial del sistema en caso
de que la fórmula se satisfaga (F9). El esquema de comunicación entre ellas seŕıa el
que ilustra la siguiente figura:



Caṕıtulo 10 - Complejidad de algunas propiedades 54

F3

F1

F2

checker
(F7 + F8)

input (φ)

F6

F4

F5

F9

input (m)

input (m)

Figura 10.6: Diagrama explicativo de las comunicaciones que se establecen en S.

En el diagrama observamos que esencialmente todas las comunicaciones se hacen
de forma que crece el ı́ndice de las máquinas, excepto los últimos mensajes que
manda F9 a todas las máquinas para que vuelvan a su estado inicial en caso de que
el checker haya determinado que la fórmula se ha satisfecho (que no dibujamos por
no hacer el diagrama más farragoso).

La clave de la construcción es aprovechar el no determinismo de las comunicacio-
nes entre los diferentes generadores de ceros y unos, pero con cierto cuidado ya que
tenemos que separar bien esa primera parte en la cual estamos simulando cuantifica-
dores universales y la segunda en la cual simulamos los cuantificadores existenciales.
Con este propósito hemos introducido dos grupos distintos de generadores: cada uno
será el encargado de generar los valores de verdad correspondientes en una fase, pero
no funcionarán nunca a la vez.

En concreto, el funcionamiento que buscamos es el siguiente. Las máquinas F1, F2

y F3 se encargarán de generar todas las posibles asignaciones de valores de verdad a
las m primeras variables de ϕ a través del no determinismo de sus comunicaciones,
y de transmit́ırselas al checker. Tras esto, será el turno de F4, F5 y F6, que gene-
rarán valores de verdad (de nuevo, aprovechando el no determinismo inherente a
sus comunicaciones) para las n últimas variables de ϕ. Con esto, el checker podrá
evaluar si ϕ se satisface. En caso de que fuera aśı, le mandaŕıa el mensaje > a F9, y
F9 mandaŕıa un mensaje FIN a todas las máquinas para que vuelvan a su estado
inicial.

Conforme a esta explicación, podemos hacer una implementación bastante sen-
cilla de las máquinas F1, F2 y F3, en la cual F1 solo genere m ceros (pues no se van
a poder usar más), F2 también genere m unos y F3 solo deje pasar hacia el checker
los m primeros literales que le lleguen. Tras procesar los 2m bits (ceros o unos)
que recibe, F3 les mandará la señal ON a F4 y F5 para que empiecen a funcionar,
pues ya habŕıa acabado la primera fase del algoritmo en la cual damos valores a las
primeras m variables. Las implementaciones las podemos ver gráficamente en las
figuras 10.7, 10.8 y 10.9.

Las implementaciones de F4, F5 y F6 seŕıan muy similares a la de F1, F2 y F3, pero



Caṕıtulo 10 - Complejidad de algunas propiedades 55

0

1

2

m− 1

m

I/0

I/0

· · ·

I/0

FIN/ε

Figura 10.7:
Generador
de ceros (F1).

0

1

2

m− 1

m

I/1

I/1

· · ·

I/1

FIN/ε

Figura 10.8:
Generador
de unos (F2).

0

1

2

m− 1

m

(1)

(2)

(m− 1)

1/1

1/1

· · ·

1/1

0/0

0/0

0/0
0/ε 1/ε

0/ε 1/ε

· · ·

0/ON 1/ON

Figura 10.9:
Intercalador
de ceros y unos (F3).

generando solo n literales, y solo cuando reciben ON de parte de F3. Gráficamente
podemos ver una implementación de esta idea en las figuras 10.10, 10.11 y 10.12.

Por su parte, F8 y F9 funcionan como en la demostración del teorema anterior:
toman primero la fórmula ϕ como input, y después recibirán m ceros o unos de
parte de F3 y n de F6, que habrán de interpretar como los valores de verdad que
se les asignan a las variables X1, X2, . . . , Xm+n de ϕ, en ese orden. En caso de
que la fórmula resulte satisfecha, env́ıan un mensaje > a F9. Y F9 solo espera
la recepción de >, y de ser aśı, env́ıa a todas las máquinas el mensaje FIN . Su
implementación es muy sencilla, similar a la que teńıamos anteriormente, y que
podemos ver gráficamente en la figura 10.13.

0 >/FIN (a todas las máquinas)

Figura 10.13: Esquema gráfico de F6.

Con todo esto ya tenemos el sistema creado, ahora tenemos que ver cómo hace-
mos la reducción. Lo primero es notar que como el checker funciona polinómicamente



Caṕıtulo 10 - Complejidad de algunas propiedades 56

0

1

2

n− 1

n

ON/0

ε/0

· · ·

ε/0

FIN/ε

Figura 10.10:
Generador
de ceros (F4).

0

1

2

n− 1

n

ON/1

ε/1

· · ·

ε/1

FIN/ε

Figura 10.11:
Generador
de unos (F5).

0

1

2

n− 1

n

(1)

(2)

(n− 1)

(n)

1/1

1/1

· · ·

1/1

0/0

0/0

0/0
0/ε 1/ε

0/ε 1/ε

· · ·

0/ε 1/ε

FIN/ε

Figura 10.12:
Intercalador
de ceros y unos (F6).

en el tamaño de ϕ (que denotamos |ϕ|), podemos decir que, dados el input ϕ y los
m + n bits que F3 manda al checker, este es capaz de decidir si ϕ se satisface con
estos valores de verdad en a lo sumo p(|ϕ|) pasos, siendo p un polinomio.

Aśı, podemos reducir el problema:

¿Para cualquier asignación de valores de verdad a X1, . . . , Xm existe una
asignación a las variables Xm+1, . . . , Xm+n de forma que se satisfaga ϕ?

al problema:

¿Para cualesquiera 3m primeros pasos de S, es capaz de volver a su configuración
inicial en, a lo sumo, 3n+ p(|ϕ|) + 9 pasos?

Estas cifras son sencillas de entender: 3m son los pasos que se necesitan para
que F1, F2 y F3 generen suficientes literales como para conseguir asignaciones de
valores de verdad para X1, . . . , Xm; 3n son los pasos usados para generar el resto
de valores de verdad y pasárselos al checker (dados por F4, F5 y F6); p(|ϕ|) es el
número de pasos en que el checker puede decidir si la fórmula se satisface; y 9 son los



Caṕıtulo 10 - Complejidad de algunas propiedades 57

pasos necesarios para que cada máquina vuelva a su estado inicial si la fórmula es
satisfecha (1 paso para que F9 mande FIN , y uno más por cada máquina al recibir
FIN).

Veamos por qué esta reducción funciona. Lo que tenemos que comprobar primero
es que realmente hay una equivalencia entre ambos problemas. Lo veremos viendo
las implicaciones en los dos sentidos.

Supongamos primero que para cualesquiera 3m primeros pasos de S hay una
secuencia de, a lo sumo, 3n+ p(|ϕ|) + 9 pasos para volver a la configuración inicial.
Entonces, en concreto, para las ejecuciones en las cuales los 3m primeros pasos
de S se los distribuyen equitativamente F1, F2 y F3 (m pasos cada máquina) para
conseguir mandar al checker m ceros o unos, se puede regresar a la configuración
inicial en 3n+p(|ϕ|)+9 pasos. Y este tipo de ejecuciones, debido al no determinismo
de las comunicaciones entre los generadores de ceros y unos y las máquinas que los
intercalan, modelizan perfectamente el problema de asignar m valores de verdad
cualesquiera a X1, . . . , Xm y comprobar si hay valores para Xm+1, . . . , Xm+n que
satisfagan ϕ. Esto demuestra la primera de las implicaciones.

Comprobemos ahora la otra implicación. Supongamos que para cualquier asigna-
ción de valores de verdad a X1, . . . , Xm existe una asignación de valores a Xm+1, . . . ,
Xm+n que satisfaga ϕ. Entonces para cualquier ejecución en la cual los 3m prime-
ros pasos los dan F1, F2 y F3 equitativamente habrá una secuencia de a lo sumo
3n+ p(|ϕ|) + 9 para volver a la configuración inicial (esto es claro por lo que vimos
en el párrafo anterior). Pero podŕıa ser que los primeros 3m pasos de S no los dieran
únicamente F1, F2 y F3. La única forma de que esto ocurriera seŕıa que el checker
diera algunos de esos pasos, pues las máquinas F4, F5 y F6 están bloqueadas hasta
que les llegue el mensaje ON , que no puede suceder en los primeros 3m pasos. Su-
pongamos entonces que, de los 3m primeros pasos, el checker da una serie de pasos
de forma que solo acaba recibiendo de F3 el valor de verdad de k < m variables.
Como k < m, podemos aplicar nuestra hipótesis para afirmar que existen valores de
verdad para las variables Xk+1, . . . ,Xm+n de forma que ϕ se satisface (en realidad
hemos cambiado m−k cuantificadores universales de la hipótesis por cuantificadores
existenciales, y esto simplifica el problema). Sabiendo esto, podemos claramente en-
contrar una secuencia de 3n+p(|ϕ|)+9 pasos de S en las cuales F1, F2 y F3 asignan
estos valores a Xk+1, . . . , Xm+n y la ejecución continúa hasta comprobar que ϕ se
satisface con dichos valores de verdad y se regresa a la configuración inicial.

Formalmente, el argumento se ha basado en la modificación de cuantificadores en
la cual se intercambian cuantificadores universales por existenciales, que lógicamente
es correcta, como podemos comprobar mediante la siguiente implicación (si k < m):

∀X1, . . . ,Xm ∃Xm+1, . . . , Xm+n tales que ϕ(X1, . . . , Xm+n)

=⇒ ∀X1, . . . , Xk ∃Xk+1, . . . , Xm+n tales que ϕ(X1, . . . , Xm+n)

Notemos aqúı que ha sido de vital importancia que F4, F5 y F6 estén bloqueadas
durante los primeros 3m pasos de S, pues de otra forma podŕıamos haber fijado
más de m valores de variables de ϕ, y a partir de ah́ı la fórmula podŕıa no ser
satisfactible.



Caṕıtulo 10 - Complejidad de algunas propiedades 58

Con esto ya hemos visto que los problemas son en realidad equivalentes: ambos
dan siempre la misma respuesta ante los mismos datos iniciales. Ahora tenemos que
comprobar que la reducción es polinómica. Esto es sencillo de ver por todo lo que
hemos ido explicando: en cuanto a tiempos de ejecución es claramente polinómica
en el tamaño del input, pues hemos visto que todo se puede resolver en 3(m+ n) +
p(|ϕ|) + 9 pasos. Además, la construcción del sistema S no depende del tamaño de
la fórmula ϕ, y el input inicial del sistema es de tamaño |ϕ|+ 2m, que es claramente
polinómico en el tamaño del input ϕ.

Visto todo lo anterior, dado que el problema QSAT2 es ΠP
2 -completo y lo he-

mos conseguido reducir polinómicamente a nuestra versión finitista del problema
de regreso a la configuración inicial, este último problema resulta asimismo ΠP

2 -
completo.

10.3. Otros problemas de complejidad mayor

En nuestro camino hemos encontrado ya varios problemas de decisión que, al
restringirlos a una versión finitista, se vuelven decidibles en el caso de los sistemas
de FSMs en comunicación. Si bien, aunque dif́ıcilmente tratables en la práctica
(pues resolver un problema ΠP

2 -completo puede resultar muy costoso), hay algunos
problemas cuya complejidad está más arriba aún en la jerarqúıa. Aqúı vamos a
ver algunos problemas que son PSPACE-completos, es decir, los más dif́ıciles de
resolver de la categoŕıa PSPACE de problemas que pueden ser resueltos por una
máquina de Turing utilizando una cantidad polinómica de memoria.

Uno de los problemas más conocidos que es PSPACE-completo es decidir si un
LBA acepta un input dado. De esta forma, dado que las simulaciones que haćıamos
en el apartado 6 mediante sistemas de FSMs en comunicación donde los outputs no
proliferan solo añad́ıan un sobrecoste polinómico en cuanto a tiempos y manteńıan
las propiedades de uso de espacio, podemos concluir simplemente que el problema
de que un sistema de FSMs en comunicación donde los outputs no proliferan llegue
a una configuración de aceptación al recibir un input es PSPACE-completo.

También es PSPACE-completo el problema de, en una red de Petri, saber si
alguna posición alcanzable tiene al menos k tokens en alguno de sus lugares, dados
k y un marcaje inicial (como se puede ver en [18]). Esta seŕıa la versión finitista
más clara del problema de la acotación, que es tan importante en sistemas en los
cuales hay comunicación. De esta forma, con la simulación que hemos explicado en
el apartado 8, deducimos también que el mismo problema seŕıa PSPACE-completo
en el caso de los sistemas de FSMs en comunicación modificados que usábamos en
8 para simular redes de Petri.

Ya vemos que no es dif́ıcil llegar a problemas PSPACE-completos inspeccionan-
do algunos de los problemas más básicos que querŕıamos poder resolver de nuestros
sistemas. Esto no debeŕıa ser en realidad muy sorprendente: ya en otros formalismos
similares, como el de las redes de Petri, que tienen un nivel de expresividad simi-
lar y han sido ampliamente estudiadas, hay una importante cantidad de problemas
interesantes que son PSPACE-completos, por ejemplo. En nuestro caso, vamos a



Caṕıtulo 10 - Complejidad de algunas propiedades 59

presentar un resultado que no se deduce directamente de las propiedades de otro
tipo de máquinas, y puede resultar interesante.

Con lo discutido en los anteriores párrafos, resulta razonable definir el problema
de la acotación finita de la siguiente forma: dado un número natural k y una confi-
guración inicial de un sistema de FSMs en comunicación, ¿hay alguna configuración
alcanzable en la cual alguno de los buffers tenga al menos k literales?

Proposición 10.5. El problema de la acotación finita para sistemas de FSMs en
comunicación es PSPACE-completo.

Demostración. Es sencillo comprobar que el problema es PSPACE: si el sistema
tiene n máquinas y k es la constante de acotación del input (que, como anterior-
mente, suponemos que viene dada en base unaria), como el sistema de FSMs no va
a tener nunca más de nk literales (en caso de que se cumpla el problema), será sen-
cillo simularlo con nk posiciones en la memoria de una máquina de Turing. Además,
codificando los buffers de cada FSM en una cinta diferente de la máquina de Turing,
es fácil darse cuenta de que podemos simular el sistema con una máquina de Tu-
ring de tamaño polinómico respecto al tamaño de nuestro sistema de FSMs (donde
este tamaño viene representado por el número de estados que tienen las distintas
máquinas). Como podemos ver, esta construcción usa una cantidad polinómica de
espacio respecto al tamaño del input y simula perfectamente el sistema de FSMs si
sus buffers están acotados; aśı que el problema es en efecto PSPACE.

Y que sea PSPACE-duro lo podemos deducir del resultado que hemos comen-
tado antes sobre la aceptación en LBAs. Por tanto, vamos a hacer una reducción de
este problema sobre aceptación en LBAs a nuestro problema de sistemas de FSMs
en comunicación, que sea además polinómica.

Para cada LBA F y palabra ω, podemos construir un sistema S de FSMs en
comunicación que lo simule, que tendrá k literales al inicio de su ejecución entre
todos los buffers. En concreto, lo haremos de forma que los outputs no proliferen.
Esto nos asegura que podemos conseguir simular todo el proceso de aceptación (o no
aceptación) de ω sin que en S aumente el número de literales entre todos los buffers
(propiedad de los sistemas donde los outputs no proliferan). Añadimos al final una
modificación a S para resolver el problema: en caso de que F acepte ω, S llegará a
una de sus configuraciones de aceptación. Y de cada una de estas configuraciones de
aceptación de S simplemente tenemos que añadir algún estado que entre en bucle a
producir literales sin parar.

De esta forma S será un sistema donde los outputs pueden proliferar, y donde de
hecho, solo habrá algún buffer que tenga al menos k+1 literales en el caso de que se
haya llegado a estos estados en los cuales se producen literales descontroladamente,
lo cual solo puede ocurrir si F acepta ω. De esta forma deducimos que S no es k+ 1
acotado si y solo si F acepta ω, y la transformación ha sido polinómica en el tamaño
de F y ω. Al ser el problema de si F acepta ω PSPACE-completo, también lo ha
de ser el de la acotación finita de sistemas de FSMs.

Con esto hemos comprobado que en sistemas de FSMs en comunicación, dada
su gran expresividad, hay problemas de gran variedad de complejidades, y tenemos



Caṕıtulo 10 - Complejidad de algunas propiedades 60

también una idea de cuál es esta complejidad para algunos de los problemas más
interesantes de los modelos concurrentes que se aplican a nuestros sistemas. Este es
por tanto un buen punto de partida al intentar usar este tipo de sistemas.



Caṕıtulo 11

Un sistema Turing universal

En la teoŕıa de computabilidad ha sido siempre un problema interesante con-
seguir máquinas de Turing universales lo más pequeñas o sencillas posible. Se han
llegado a construir máquinas muy pequeñas: ya en 1962 M. Minsky encontró una con
únicamente 7 estados y un alfabeto de 4 śımbolos, y esto ha ido mejorándose hasta
llegar, por ejemplo, a una máquina con solo 2 estados (aunque 18 śımbolos en el
alfabeto) u otra con 3 estados y 9 literales en su alfabeto (ambas propuestas por Y.
Rogozhin en 1996 [24]). Relajando la noción de Turing completitud a máquinas de
Turing que usan una cinta inicial un tanto modificada, que no tenga a ambos lados
infinitos śımbolos de blanco (como vamos a ver en la teoŕıa que desarrollaremos en
las siguientes páginas), se han llegado a conseguir máquinas de Turing universales
con solo 2 estados y 4 śımbolos en el alfabeto (por T. Neary y D. Woods en 2007
[22]); resultados que ya son bastante dif́ıciles de superar, e incluso podŕıa ser que en
algunos casos fueran óptimos.

En nuestro caso, vamos a construir un sistema de FSMs en comunicación con 36
estados en total que sea universal, y que tenga un alfabeto con solo 3 literales. No
supone ni mucho menos un número tan bajo como los récords que comentábamos
antes, pero supone un resultado interesante en términos de simplicidad: esencial-
mente el funcionamiento del sistema está concentrado en únicamente 4 estados, y
la mayoŕıa del resto estarán casi repetidos, pues tendrán una estructura muy bien
definida que vamos a iterar. Consideramos por tanto interesante este resultado por-
que resulta mucho más intuitivo de entender que muchas otras de las máquinas que
en su momento constituyeron un récord, que son más artificiales en cuanto a sus
métodos de construcción y se entiende, por tanto, peor la forma en que funcionan.

La construcción que haremos está basada en el autómata 110, un autómata celu-
lar cuyo comportamiento aparentemente sencillo contrasta con la propiedad básica
por la cual es conocido: es Turing completo.

Recordemos que los autómatas celulares son aquellos que tienen una serie de
posiciones (normalmente con formas regulares, como en forma de cuadŕıcula o ali-
neados), pudiendo estar cada posición en una cantidad finita de estados en cada
instante. Y estos autómatas van evolucionando con el tiempo de forma que el es-
tado de cada posición en el tiempo t + 1 depende únicamente de del estado de sus
posiciones vecinas en el instante t (siendo esta relación de vecindad y la forma de
cambiar de cada posición diferente en cada autómata).

En este sentido, el autómata 110 simplemente opera en paralelo sobre un vector
infinito de celdas (que podemos ver como la cinta de una máquina de Turing), de

61



Caṕıtulo 11 - Un sistema Turing universal 62

forma que en cada movimiento genera una nueva cinta completa, en la cual cada
posición depende únicamente de su valor en la cinta en el instante anterior y la
de sus dos posiciones inmediatamente adyacentes. El alfabeto de cinta se supone
binario (aqúı trabajaremos con 0 y 1). Las transiciones se pueden ver en la siguiente
tabla, que muestra cuál es el valor de una celda en el instante t+ 1 sabiendo el valor
que teńıan sus 3 celdas vecinas en el instante t (la de su izquierda, ella misma y la
de su derecha, en ese orden):

Cinta en t 111 110 101 100 011 010 001 000

Cinta en t+ 1 0 1 1 0 1 1 1 0

Si interpretamos estas transiciones como un número en decimal, resulta ser el
110 (de un total de 256 autómatas diferentes que podŕıan definirse del mismo modo),
de ah́ı el nombre del autómata.

Para simular el comportamiento del autómata 110, usaremos un enfoque similar
al del apartado 6.2, en el cual nuestro sistema barŕıa de izquierda a derecha la cinta
de la máquina de Turing, generando aśı una nueva cinta tras cada barrido. En este
caso se aplica también la idea de retrasar los outputs un ciclo respecto a los inputs:
antes era porque el cabezal pod́ıa moverse a la izquierda, y ahora es debido a que
cada letra puede afectar a la que está a su izquierda cuando el autómata genere un
output para la siguiente posición de la cinta. Visto de otro modo, a la hora de ir
recorriendo de izquierda a derecha la cinta, hemos de recordar los dos valores que
acabamos de ver, y solo a la hora de ver el tercero tomaremos la decisión de sacar un
output, que estará un ciclo retrasado conforme a la idea que propone el autómata
110 (podŕıamos decir que el nuevo valor de una celda se genera cuando visitamos el
valor antiguo de su vecina derecha), si bien no supone un problema.

A modo de ejemplo tenemos la figura 11.1: si ati representa el contenido de la
posición i de la cinta en el instante t, entonces las flechas diagonales lisas indican
cuándo se genera cada literal de la cinta de t = 1, mientras que las flechas disconti-
nuas nos indican qué otras posiciones hemos tenido que tener en cuenta para generar
dicha posición, y que por lo tanto, de alguna manera nuestro sistema ha de recordar.

a0
0 a0

1 a0
2 a0

3 a0
4

a1
0 a1

1 a1
2 a1

3 a1
4

Figura 11.1: Representación gráfica de cómo se retrasan las producciones.

Resulta necesario pensar también en una forma de delimitar la cinta actual, pues
no queremos que el final de la cinta en el instante t influya en los outputs generados



Caṕıtulo 11 - Un sistema Turing universal 63

al inicio de la cinta del instante t+ 1. Para ello introduciremos el literal #, como ya
hicimos anteriormente, que denotará el fin de una cinta y, a la vez, el comienzo de
la siguiente.

Con estas ideas, podŕıamos crear un autómata bastante sencillo que simule el
funcionamiento del autómata 110, como representamos en la siguiente figura:

#

0

1

00 01

10 11

0/ε

1/ε

0/ε

1/ε

0/ε

1/ε

0/0

1/1

0/1

1/10/0

1/1

0/1

1/0

#/#

#/#

#/#

#/#

#/#

#/#

#/#

Figura 11.2: Implementación de la FSM que simula las producciones del autómata
110.

Como vemos, esencialmente estos 7 estados ya aglutinan el funcionamiento del
autómata 110, y por tanto simulan algo que tiene tanta expresividad como para ser
Turing completo. Además, los 4 estados 00, 01, 10, 11 son los que llevan la mayor
parte del significado, pues los otros 3 solo reflejan una especie de estado transitorio
del sistema, en el cual todav́ıa no hemos léıdo suficientes caracteres como para
generar un output.

Pero ahora se nos presenta la mayor dificultad de la construcción: la demostra-
ción de que el autómata 110 es Turing completo, llevada a cabo por Matthew Cook
en 2004 [8, 9] para dar una contestación positiva a la conjetura de Stephen Wolfram
en 1985, presupone que la cinta es un poco diferente a lo que estamos acostumbra-
dos: no está rellena entera de caracteres blancos a izquierda y derecha de la zona
que estamos tratando, sino que supone que hay un patrón repetitivo que se repite
indefinidamente hacia izquierda y derecha. Cook llama a este patrón repetitivo éter,
y es la cadena 00010011011111, de longitud 14. Al aplicar la regla del autómata
110 sobre el éter, este se desplaza 4 posiciones a la izquierda. De este modo, tras
7 iteraciones, obtenemos de nuevo el éter en su posición inicial, y todo se repite
ćıclicamente.



Caṕıtulo 11 - Un sistema Turing universal 64

0 0 0 1 0 0 1 1 0 1 1 1 1 1 0 0 0 1

0 0 1 1 0 1 1 1 1 1 0 0 0 11000

· · · · · ·

· · · · · ·

Figura 11.3: Una iteración de la evolución del éter.

Lo que nos falta entonces para conseguir que nuestro sistema simule realmente
el autómata 110 de forma que consigamos un sistema Turing universal es, de alguna
forma, simular el éter. Para ello introduciremos dos máquinas adicionales: una si-
mulará la creación de éter a la derecha de la zona de la cinta que estamos tratando
(F2), y otra a la izquierda (F0). La máquina que simulaba el autómata 110 y que
hemos explicado en la figura anterior será la máquina F1. Tendremos por tanto un
sistema S con 3 máquinas que se comunicarán de manera ćıclica: F0 le mandará la
cinta completa a F1, F1 a F2 la nueva cinta generada, F2 a F0 la cinta habiendo
añadido un carácter por la derecha, y cuando le llegue de nuevo a F1 a través de F0,
esta habrá añadido un carácter más del éter por la izquierda. Como comentamos,
tras cada barrido de la cinta, tanto F0 como F2 añadirán un carácter nuevo a la
cadena que está procesando el sistema S. Esto hace que cada vez haya más literales
en S y que no todos sean especialmente relevantes (pues la mayoŕıa van a continuar
siguiendo el patrón del éter, porque las modificaciones no se han extendido tanto).
Sin embargo, es una manera fácil de resolver la cuestión de la simulación del éter,
porque si no, tendŕıamos que crear un método de detección de qué zonas de la cinta
han cambiado o no en cada momento, lo cual resultaŕıa mucho más costoso.

Sin más dilación, pasamos a definir F0. Como forzosamente el sistema tiene que
recordar en cuál de los 14 elementos del periodo del éter está (por la izquierda en este
caso), F0 tiene que tener al menos 14 estados. Veamos que basta con 14: definimos
un estado qi (para cada i ∈ {0, . . . , 13}) de forma que si F0 está en el estado qi, esto
significa que el siguiente literal a la izquierda de la región de la cinta que la máquina
F1 ha considerado hasta ahora es el i-ésimo del patrón del éter, que recordemos que
es 00010011011111. Como sabemos que, tras una pasada de las máquinas, el éter se
desplaza 4 posiciones a la izquierda. Eso nos quiere decir que, si en el tiempo t en
una posición de la cinta estábamos en el carácter i del éter, en el instante t+1 en esa
posición estará el carácter i+ 4 (módulo 14, claro). Pero como ese carácter lo habrá
introducido F0 en el sistema en tiempo t, y ahora estamos interesados en el carácter
justo a su izquierda, es decir, en el i + 3 del éter. Por tanto, de qi transitaremos a
q(i+3) mód 14. Con esto se nos crea una estructura muy regular y sencilla que nos
permite generar éter paso a paso a la izquierda de la zona que está tratando nuestro
sistema hasta el momento.

Una vez tenemos esto claro, solo tenemos que darnos cuenta de cuál es el funcio-
namiento que esperamos de F0: debeŕıa reenviar todo lo que lee, y únicamente añadir
una letra en la siguiente cinta, es decir, que solo añade la letra correspondiente del
éter cuando le llega el carácter # (lo cual hacemos, por simplicidad, generando 2
outputs al consumir el input #, lo cual vimos ya tras la definición 5.1 que era una



Caṕıtulo 11 - Un sistema Turing universal 65

forma razonable de interpretar el fenómeno subyacente de proliferación de los out-
puts). Todo este pensamiento quedaŕıa plasmado en un autómata de la forma que
mostramos en la figura 11.4.

q0

q1

q2

q3

q4

q5

q6

q7

q8

q9

q10

q11

q12

q13

0/0

1/1

0/0

1/1

0/0

1/1

0/0

1/1

0/0

1/1

0/0

1/1

0/0

1/1

0/0

1/1

0/0

1/1

0/0

1/1

0/0

1/1

0/0

1/1

0/0

1/1

0/0

1/1

#/#0

#/#0

#/#0

#/#1

#/#0

#/#0

#/#1

#/#1

#/#0

#/#1

#/#1

#/#1
#/#1

#/#1

Figura 11.4: Implementación de F0 en la construcción.

Una vez entendida la construcción del autómata F0, la construcción de F2 resul-
ta sencilla por analoǵıa. Las transiciones cambiarán poco, pues desde el estado qi
transitaremos al q(i+5) mód 14 porque estamos interesados en la posición a la derecha
de la i + 4, no en la izquierda como en F0. Y de nuevo, F2 solo añade literales al
sistema una vez sabe que le ha llegado el fin de la cinta, es decir, cuando lee #. Esto
nos daŕıa el autómata de la figura 11.5.



Caṕıtulo 11 - Un sistema Turing universal 66

q0 q1 q2 q3 q4

q5 q6 q7 q8 q9

q10 q11 q12 q13 q′8

0/0

1/1

0/0

1/1

0/0

1/1

0/0

1/1

0/0

1/1

0/0

1/1

0/0

1/1

0/0

1/1

0/0

1/1

0/0

1/1

0/0

1/1

0/0

1/1

0/0

1/1

0/0

1/1

#/0# #/0# #/0# #/1# #/0#

#/0# #/1# #/1# #/0

−/#

#/1#

#/1# #/1# #/1#
#/1#

Figura 11.5: Implementación de F2 en la construcción.

Por último, comentamos cómo se inicia todo el procedimiento de simulación:
en F1 el estado inicial es #; en F0 es q0; y en F2 es q′8 (que hemos separado de
q8 para que al inicio solo se produzca la # que necesitamos). Además, el input se
pondrá en el buffer del que lee F2. Aśı, habrá una primera vuelta en la cual F2

añade # y F0 y F2 la reenv́ıan. Por tanto, el buffer de F2 ahora tendrá el input
inicial seguido de #. Y con eso ya empieza el reconocimiento usual, y F2 empieza a
añadir caracteres correctamente porque está en q13 (y el éter va hacia la izquierda),
y F0 estaba añadiendo partes correctas del éter desde el principio.



Caṕıtulo 12

Conclusiones

A la vista de todo el trabajo expuesto hasta ahora, ya podemos extraer varias
conclusiones interesantes sobre los sistemas de máquinas de estados finitos en co-
munciación. Lo primero que hemos comprobado es que dentro del mismo marco
teórico tienen cabida diferentes definiciones, y cada una de ellas implica diferen-
tes propiedades de los sistemas. En concreto, las versiones más usuales tienen una
expresividad bastante alta y están siempre en la ĺınea entre lo decidible y lo indeci-
dible (como hemos visto en los caṕıtulos 4, 6, 8 y 9). El hecho de que estén en esta
frontera motiva la variedad de definiciones que tenemos: dependiendo del caso es-
taremos interesados en una ganancia en expresividad o en comprensión de nuestros
sistemas, y elegiremos versiones en uno u otro lado de la frontera dependiendo de
estos intereses.

En concreto, sabemos que los sistemas de máquinas de estados generales son Tu-
ring completos (caṕıtulo 4) y eso hace que los problemas de decisión asociados a ellos
sean indecidibles (Teorema de Rice). Pero además, versiones simplificadas de estos
problemas de decisión (que hemos estudiado en el caṕıtulo 10) son también dif́ıciles
de resolver en general, como el caso de la alcanzabilidad finita, que hemos compro-
bado que es NP-completo. Además, por ser Turing completo, podemos construir
sistemas que sean universales. En este caso ha sido interesante la construcción ba-
sada en el autómata 110 (caṕıtulo 11) por ser simple y sencilla de entender, además
de relativamente pequeña.

Respecto a las diferentes modificaciones podemos decir también varias cosas.
Sabemos que los sistemas donde los outputs no proliferan son completos dentro de
los reconocedores de lenguajes dependientes del contexto, lo que los sitúa cerca de la
Turing completitud, pero hace que sean más sencillos de estudiar a pesar de esa gran
expresividad. En concreto hemos podido comprobar que algunos problemas de vital
importancia, como el de saber si aceptan un input dado, es decidible, aunque tiene
una complejidad muy elevada (vimos que era PSPACE-completo en el caṕıtulo 10).

El caso de los sistemas donde los buffers están acotados es más sencillo. Com-
probamos que son equivalentes a los autómatas finitos en el caṕıtulo 7 y que eso
hace que problemas anteriormente estudiados como la alcanzabilidad finita sean
polinómicos (en el caṕıtulo 10).

Era más interesante el caso de los sistemas donde los buffers no tienen orden,
estudiados en el caṕıtulo 8. En este caso, diferentes adaptaciones de la definición
llevaban a la equivalencia con diferentes redes de Petri: las usuales, con arcos in-
hibidores o con arcos restablecedores. En todos los casos resultaba interesante la

67



Caṕıtulo 12 - Conclusiones 68

comparativa entre la complejidad de ciertos problemas básicos como la alcanzabili-
dad o el recubrimiento, que están en la frontera de lo decidible e indecidible en estos
tres tipos de redes de Petri, como vimos al final del caṕıtulo.

Por último estudiamos una variación en la cual los canales de comunicación
pueden fallar, dando lugar al formalismo (ampliamente estudiado en la literatura)
de los Sistemas de Mensajes Perdidos. Hemos recopilado algunos de las propiedades
básicas de estos sistemas en el caṕıtulo 9, como que el problema de la terminación
es decidible (aunque de una complejidad extremadamente alta).

Con esto hemos establecido una teoŕıa básica bastante amplia sobre sistemas
formados por máquinas de estados finitos en comunicación, que puede servir en mu-
chos otros trabajos como referencia de qué propiedades son esperables dependiendo
de las caracteŕısticas que tengan nuestros canales de comunicación. Además hemos
expuesto una colección bastante amplia de variaciones en la definición principal, de
forma que todos estos modelos se podrán reutilizar en casos en los que tengamos
que implementar protocolos en los cuales máquinas sencillas tienen que comunicarse
para realizar una tarea más compleja.



Conclusions

From the work that has been done we can already draw several interesting con-
clusions about communicating Finite State Machines. The first thing that has be-
come clear through all these pages is that several definitions are possible under this
abstract framework, and each of them has different properties. The most usual defi-
nitions are on the edge between decidability and undecidability and have very high
expressivity (as we have seen in Chapters 4, 6, 8 and 9). The fact of being in that
frontier motivates the variability of definitions we have introduced: depending on
the situation we will be interested in a more expressive model or in a model where
properties are easier to comprehend.

In particular we can affirm that the general model of communicating Finite
State Machines are Turing complete (seen in chapter 4), and that makes its decision
problems to be undecidable (Rice’s Theorem). Moreover, some simplified versions of
those decision problems are still quite difficult to solve: for instance we have proved
that a finitary version of reachability is NP-complete in chapter 10. Furthermore,
due to being Turing complete, we can construct universal systems. We exploit this
in chapter 11, getting a fairly simple system (yet small) by simulating Rule 110.

Regarding the different modifications on the definition, we can also say some
interesting things. In the case of the systems where outputs are not allowed to
spread, we have verified that they are complete among the context-sensitive language
recognizers. Thus they are a really expressive model (close to Turing machines) but
easier to study in terms of their decidable properties. Concretely we have confirmed
that some crucial properties such as the word problem are decidable, though their
complexity is really high (in chapter 10 we saw it was in fact PSPACE-complete).

The case of systems where the buffers used to communicate are bounded turned
out to be easy to study. In chapter 7 we found that they were equivalent to finite
automata and that makes some decision problems easy, as in the case of the finitary
reachability, which we proved to be polynomial in chapter 10.

The case where the order inside those buffers is suppressed, studied in chapter
8, is more interesting: different definitions led to equivalences with different kinds
of Petri nets: the usual ones, with inhibitor arcs or with reset arcs. In all these
cases it was interesting to compare how some basic problems -such as reachability
or coverability- are on the thin edge between decidable or undecidable depending
on the definitions.

Lastly we studied a modification where the communication channels are faulty,
leading us to the -well studied in the literature- model of Lossy Channel Systems. We
have summed up some of the most important and basic properties of these systems
in chapter 9. For instance, the problem of termination becomes -possibly a priori
counterintuitively- decidable, though having an extremely high complexity.

69



Caṕıtulo 12 - Conclusiones 70

With all this we have set a basic theory on communicating Finite State Machines
which is fairly broad: it can be useful in many other works as a reference to know
what to expect of a system depending on the properties of our channels of com-
munications. Furthermore we have provided a wide spectrum of possible variations
which can also be reused to implement different protocols where simple machines
are supposed to communicate to perform a more difficult task.



Bibliograf́ıa

[1] P. Abdulla y B. Jonsson. ((Undecidable Verification Problems for Programs
with Unreliable Channels)). En: Information and Computation 130.1 (1996),
págs. 71-90. doi: https://doi.org/10.1006/inco.1996.0083.

[2] P. Abdulla y B. Jonsson. ((Verifying Programs with Unreliable Channels)). En:
Information and Computation 127 (1996), págs. 91-101.

[3] T. Agerwala. ((A Complete Model for Representing the Coordination of Asyn-
chronous Processes)). En: Hopkins Computer Research Reports 32 (1974).

[4] T. Araki y T. Kasami. ((Some decision problems related to the reachabi-
lity problem for Petri nets)). En: Theoretical Computer Science 3.1 (1976),
págs. 85-104. issn: 0304-3975. doi: https : / / doi . org / 10 . 1016 / 0304 -

3975(76)90067-0.

[5] M. Blondin, A. Finkel y P. McKenzie. ((Handling infinitely branching well-
structured transition systems)). En: Information and Computation 258 (2017).
doi: 10.1016/j.ic.2017.11.001.

[6] G. Bochmann. ((Finite State Description of Communication Protocols)). En:
Computer Networks 2 (1978), págs. 361-372.

[7] D. Brand y P. Zafiropulo. ((On Communicating Finite State Machines)). En:
Journal of the Asociation for Computing Machinery 30.2 (1983), págs. 323-342.

[8] M. Cook. ((A Concrete View of Rule 110 Computation)). En: The Complexity
of Simple Programs 15 (2009), págs. 31-55. doi: 10.4204/EPTCS.1.4.

[9] M. Cook. ((Universality in Elementary Cellular Automata)). En: Complex Sys-
tems 15 (2004), págs. 1-40.

[10] G. Dı́az, J. Mateo, P. Rabanal e I. Rodŕıguez. ((A centralized and a decen-
tralized method to automatically derive choreography-conforming web ser-
vice systems)). En: J. Log. Algebr. Program. 81 (2012), págs. 127-159. doi:
10.1016/j.jlap.2011.10.001.

[11] C. Dufourd, A. Finkel y Ph. Schnoebelen. ((Reset nets between decidability
and undecidability)). En: Proc. 25th. Int. Coll. Automata, Languages and Pro-
gramming 1443 (1998), págs. 103-115.

[12] J. Esparza. Petri Nets, Lecture Notes. 2017.

[13] M. Gouda, E. Manning e Y. Yu. ((On the progress of communication between
two machines)). En: (oct. de 1980), págs. 369-389. doi: 10.1007/3- 540-

11604-4_62.

[14] M. Gouda y L. Rosier. ((Communicating finite state machines with priority
channels)). En: Paredaens J. (eds) Automata, Languages and Programming.
ICALP 1984. Lecture Notes in Computer Science 172 (1984).

71

https://doi.org/https://doi.org/10.1006/inco.1996.0083
https://doi.org/https://doi.org/10.1016/0304-3975(76)90067-0
https://doi.org/https://doi.org/10.1016/0304-3975(76)90067-0
https://doi.org/10.1016/j.ic.2017.11.001
https://doi.org/10.4204/EPTCS.1.4
https://doi.org/10.1016/j.jlap.2011.10.001
https://doi.org/10.1007/3-540-11604-4_62
https://doi.org/10.1007/3-540-11604-4_62


BIBLIOGRAFÍA 72

[15] M. Gouda e Y. Yu. ((Deadlock Detection for a Class of Communicating Finite
State Machines)). En: IEEE Transactions on Communications 30.12 (1982),
págs. 2514-2518.

[16] M. Gouda e Y. Yu. ((Unboundedness detection for a class of communica-
ting finite-state machines)). En: Information Processing Letters 17.5 (1983),
págs. 235-240. doi: https://doi.org/10.1016/0020-0190(83)90105-9.

[17] J. Hopcroft y J. Ullman. Introduction to Automata Theory, Languages and
Computation. Addison-Wesley series in Computer Science. Addison-Wesley,
1979.

[18] N. Jones, L. Landweber y E. Lien. ((Complexity of some problems in Petri
nets)). En: Theoretical Computer Science 4.3 (1977), págs. 277-299. doi: 10.
1016/0304-3975(77)90014-7.

[19] D. Kozen. Automata and Computability. Undergraduate Texts in Computer
Science. Springer, 1997.

[20] B. Masson y Ph. Schnoebelen. ((On Verifying Fair Lossy Channel Systems)).
En: Lecture Notes in Computer Science (2002). doi: 10.1007/3-540-45687-
2_45.

[21] R. Mayr. ((Undecidable problems in unreliable computations)). En: Lecture No-
tes in Computer Science 1776 (2003), págs. 377-386. doi: 10.1007/10719839_
37.

[22] T. Neary y D. Woods. ((Small weakly universal Turing machines)). En: CoRR
abs/0707.4489 (2007). url: http://arxiv.org/abs/0707.4489.

[23] J. Pachl. ((Reachability problems for communicating finite state machines)).
En: Computing Research Repository - CORR (2003). url: arxiv.org/abs/
cs/0306121v2.

[24] Y. Rogozhin. ((Small universal Turing machines)). En: Theoretical Computer
Science 168.2 (1996), págs. 215-240.

[25] Louis E. Rosier y Hsu-Chun Yen. ((Boundedness, empty channel detection, and
synchronization for communicating finite automata)). En: Theoretical Compu-
ter Science 44 (1986), págs. 69-105. doi: https://doi.org/10.1016/0304-
3975(86)90110-6.

[26] Ph. Schnoebelen. ((Verifying lossy channel systems has nonprimitive recursive
complexity)). En: Information Processing Letters 83 (2002), págs. 251-261. doi:
10.1016/S0020-0190(01)00337-4.

[27] Ph. Schnoebelen. ((Verifying lossy channel systems has nonprimitive recursive
complexity)). En: Information Processing Letters 83 (2002), págs. 251-261. doi:
10.1016/S0020-0190(01)00337-4.

[28] D. A. Wolfram. ((Solving generalized Fibonacci recurrences)). En: The Fibo-
nacci Quarterly 36 (1997), págs. 129-145.

https://doi.org/https://doi.org/10.1016/0020-0190(83)90105-9
https://doi.org/10.1016/0304-3975(77)90014-7
https://doi.org/10.1016/0304-3975(77)90014-7
https://doi.org/10.1007/3-540-45687-2_45
https://doi.org/10.1007/3-540-45687-2_45
https://doi.org/10.1007/10719839_37
https://doi.org/10.1007/10719839_37
http://arxiv.org/abs/0707.4489
arxiv.org/abs/cs/0306121v2
arxiv.org/abs/cs/0306121v2
https://doi.org/https://doi.org/10.1016/0304-3975(86)90110-6
https://doi.org/https://doi.org/10.1016/0304-3975(86)90110-6
https://doi.org/10.1016/S0020-0190(01)00337-4
https://doi.org/10.1016/S0020-0190(01)00337-4

	Introducción
	Estado del arte
	Definición de los sistemas con 2 máquinas
	Sistemas donde los outputs no proliferan

	Expresividad de los sistemas
	Definición general de los sistemas
	Sistemas con buffers acotados

	Sistemas donde los outputs no proliferan
	Ejemplo de funcionamiento
	Expresividad de los sistemas donde los outputs no proliferan

	Sistemas con buffers acotados
	Sistemas con buffers sin orden
	Expresividad de los sistemas con buffers sin orden
	Comparativa con otros tipos de redes de Petri

	Sistemas de Mensajes Perdidos
	Introduciendo justicia en las ejecuciones

	Complejidad de algunas propiedades
	El problema de la alcanzabilidad finita
	En sistemas con buffers acotados

	El problema de regreso al estado inicial
	Otros problemas de complejidad mayor

	Un sistema Turing universal
	Conclusiones