Download Variedades y covariedades de lenguajes

VARIEDADES Y COVARIEDADES DE LENGUAJES
Congreso de Jóvenes Investigadores, RSME
Sevilla, 2013
Enric Cosme-Llópez
Departament d'Àlgebra
Universitat de València
PRELIMINARES
Preliminares
Autómatas distinguidos
Ecuaciones y coecuaciones
Variedades y covariedades
AUTÓMATA
Definición
Sea A un alfabeto finito. Un autómata es un par (X, α) consistente en un conjunto X de estados (posiblemente infinito) y una
función de transición
α : X → XA
3
Preliminares
Autómatas distinguidos
Ecuaciones y coecuaciones
Variedades y covariedades
AUTÓMATA
Definición
Sea A un alfabeto finito. Un autómata es un par (X, α) consistente en un conjunto X de estados (posiblemente infinito) y una
función de transición
α : X → XA
Utilizaremos la siguiente notación:
x
a
y
⇔
α(x)(a) = y
3
Preliminares
Autómatas distinguidos
Ecuaciones y coecuaciones
Variedades y covariedades
AUTÓMATA
Definición
Sea A un alfabeto finito. Un autómata es un par (X, α) consistente en un conjunto X de estados (posiblemente infinito) y una
función de transición
α : X → XA
Utilizaremos la siguiente notación:
x
a
y
⇔
α(x)(a) = y
También escribiremos xa = α(x)(a) y, de forma más general,
xε = x
xwa = α(xw )(a)
3
Preliminares
Autómatas distinguidos
Ecuaciones y coecuaciones
Variedades y covariedades
AUTÓMATAS PUNTEADOS Y COLOREADOS
Definición
Un autómata puede tener estado inicial x ∈ X. Representado por
una función
x:1→X
Llamaremos a la tupla (X, α, x) autómata punteado
4
Preliminares
Autómatas distinguidos
Ecuaciones y coecuaciones
Variedades y covariedades
AUTÓMATAS PUNTEADOS Y COLOREADOS
Definición
Un autómata puede tener estado inicial x ∈ X. Representado por
una función
x:1→X
Llamaremos a la tupla (X, α, x) autómata punteado
Definición
Un estado también puede ser final o no. Representado por una
función
c:X→2
Diremos que el estado x es final si c(x) = 1 y llamaremos a la
tupla (X, α, c) autómata coloreado.
4
Preliminares
Autómatas distinguidos
Ecuaciones y coecuaciones
Variedades y covariedades
DIAGRAMA
Todos estos objetos pueden representarse mediante el diagrama:
1
x
c
2
X
α
XA
5
Preliminares
Autómatas distinguidos
Ecuaciones y coecuaciones
Variedades y covariedades
DIAGRAMA
Todos estos objetos pueden representarse mediante el diagrama:
1
x
c
2
X
α
XA
6
Preliminares
Autómatas distinguidos
Ecuaciones y coecuaciones
Variedades y covariedades
DIAGRAMA
Todos estos objetos pueden representarse mediante el diagrama:
1
x
c
2
X
α
XA
7
AUTÓMATAS DISTINGUIDOS
Preliminares
Autómatas distinguidos
Ecuaciones y coecuaciones
Variedades y covariedades
ÁLGEBRA INICIAL
El conjunto A∗ forma un autómata punteado (A∗ , σ, ε) con estado
inicial ε y función de transición definida por
σ : A∗ → (A∗ )A σ(w)(a) = wa
9
Preliminares
Autómatas distinguidos
Ecuaciones y coecuaciones
Variedades y covariedades
ÁLGEBRA INICIAL
El conjunto A∗ forma un autómata punteado (A∗ , σ, ε) con estado
inicial ε y función de transición definida por
σ : A∗ → (A∗ )A σ(w)(a) = wa
Proposición
(A∗ , σ, ε) es un álgebra inicial.
9
Preliminares
Autómatas distinguidos
Ecuaciones y coecuaciones
Variedades y covariedades
ÁLGEBRA INICIAL
El conjunto A∗ forma un autómata punteado (A∗ , σ, ε) con estado
inicial ε y función de transición definida por
σ : A∗ → (A∗ )A σ(w)(a) = wa
Proposición
(A∗ , σ, ε) es un álgebra inicial.
Para todo autómata (X, α) y cualquier elección de estado inicial
x : 1 → X, induce un único homomorfismo rx : A∗ → X, dado por
rx (w) = xw
9
Preliminares
Autómatas distinguidos
Ecuaciones y coecuaciones
Variedades y covariedades
COÁLGEBRA FINAL
∗
El conjunto 2A de lenguajes forma un autómata coloreado
∗
(2A , τ, ε?) con función de coloración ε? definida por
1 si ε ∈ L
A∗
ε? : 2 → 2
ε?(L) =
0 en otro caso
10
Preliminares
Autómatas distinguidos
Ecuaciones y coecuaciones
Variedades y covariedades
COÁLGEBRA FINAL
∗
El conjunto 2A de lenguajes forma un autómata coloreado
∗
(2A , τ, ε?) con función de coloración ε? definida por
1 si ε ∈ L
A∗
ε? : 2 → 2
ε?(L) =
0 en otro caso
y función de transición dada por
∗
∗
τ : 2A → (2A )A τ (L)(a) = La = {v ∈ A∗ | av ∈ L}
10
Preliminares
Autómatas distinguidos
Ecuaciones y coecuaciones
Variedades y covariedades
COÁLGEBRA FINAL
∗
El conjunto 2A de lenguajes forma un autómata coloreado
∗
(2A , τ, ε?) con función de coloración ε? definida por
1 si ε ∈ L
A∗
ε? : 2 → 2
ε?(L) =
0 en otro caso
y función de transición dada por
∗
∗
τ : 2A → (2A )A τ (L)(a) = La = {v ∈ A∗ | av ∈ L}
Proposición
∗
(2A , τ, ε?) es una coálgebra final.
10
Preliminares
Autómatas distinguidos
Ecuaciones y coecuaciones
Variedades y covariedades
COÁLGEBRA FINAL
∗
El conjunto 2A de lenguajes forma un autómata coloreado
∗
(2A , τ, ε?) con función de coloración ε? definida por
1 si ε ∈ L
A∗
ε? : 2 → 2
ε?(L) =
0 en otro caso
y función de transición dada por
∗
∗
τ : 2A → (2A )A τ (L)(a) = La = {v ∈ A∗ | av ∈ L}
Proposición
∗
(2A , τ, ε?) es una coálgebra final.
Para todo autómata (X, α) y cualquier elección de función de
coloración c : X → 2, induce un único homomorfismo
∗
oc : X → 2A , dado por
oc (x) = {w ∈ A∗ | c(xw ) = 1}
10
Preliminares
Autómatas distinguidos
Ecuaciones y coecuaciones
Variedades y covariedades
DIAGRAMA
En suma,
1
x
c
ε
A∗
σ
(A∗ )A
2
ε?
rx
X
oc
rxA
∗
τ
α
XA
2A
∗
(oc
)A
(2A )A
11
ECUACIONES Y COECUACIONES
Preliminares
Autómatas distinguidos
Ecuaciones y coecuaciones
Variedades y covariedades
ECUACIÓN
Definición
Un conjunto de ecuaciones es una congruencia a derecha E ⊆
A∗ × A∗ en el autómata inicial (A∗ , σ).
13
Preliminares
Autómatas distinguidos
Ecuaciones y coecuaciones
Variedades y covariedades
ECUACIÓN
Definición
Un conjunto de ecuaciones es una congruencia a derecha E ⊆
A∗ × A∗ en el autómata inicial (A∗ , σ).
Definición
Diremos que el autómata punteado (X, α, x) satisface E
(X, α, x) |= E
⇔ ∀(v, w) ∈ E, xv = xw
13
Preliminares
Autómatas distinguidos
Ecuaciones y coecuaciones
Variedades y covariedades
ECUACIÓN
Definición
Un conjunto de ecuaciones es una congruencia a derecha E ⊆
A∗ × A∗ en el autómata inicial (A∗ , σ).
Definición
Diremos que el autómata punteado (X, α, x) satisface E
(X, α, x) |= E
⇔ ∀(v, w) ∈ E, xv = xw
Definimos:
(X, α) |= E
⇔ ∀x : 1 → X, (X, α, x) |= E
13
Preliminares
Autómatas distinguidos
Ecuaciones y coecuaciones
Variedades y covariedades
ECUACIONES
Sean v, w ∈ A∗ , consideramos la abreviatura v = w para denotar
la menor congruencia a derecha en A∗ que contiene (v, w).
14
Preliminares
Autómatas distinguidos
Ecuaciones y coecuaciones
Variedades y covariedades
ECUACIONES
Sean v, w ∈ A∗ , consideramos la abreviatura v = w para denotar
la menor congruencia a derecha en A∗ que contiene (v, w).
Ejemplo
a
b
y
x
a
b
14
Preliminares
Autómatas distinguidos
Ecuaciones y coecuaciones
Variedades y covariedades
ECUACIONES
Sean v, w ∈ A∗ , consideramos la abreviatura v = w para denotar
la menor congruencia a derecha en A∗ que contiene (v, w).
Ejemplo
a
b
y
x
a
b
(X, α, x) |= {b = ε, ab = ε, aa = a}
14
Preliminares
Autómatas distinguidos
Ecuaciones y coecuaciones
Variedades y covariedades
ECUACIONES
Sean v, w ∈ A∗ , consideramos la abreviatura v = w para denotar
la menor congruencia a derecha en A∗ que contiene (v, w).
Ejemplo
a
b
y
x
a
b
(X, α, x) |= {b = ε, ab = ε, aa = a}
(X, α, y) |= {a = ε, ba = ε, bb = b}
14
Preliminares
Autómatas distinguidos
Ecuaciones y coecuaciones
Variedades y covariedades
COECUACIONES
Definición
∗
Un conjunto de coecuaciones es un subautómata D ≤ 2A del
∗
autómata final (2A , τ ).
15
Preliminares
Autómatas distinguidos
Ecuaciones y coecuaciones
Variedades y covariedades
COECUACIONES
Definición
∗
Un conjunto de coecuaciones es un subautómata D ≤ 2A del
∗
autómata final (2A , τ ).
Definición
Diremos que el autómata (X, α, c) satisface D
(X, α, c) |= D ⇔ ∀x ∈ X, oc (x) ∈ D
15
Preliminares
Autómatas distinguidos
Ecuaciones y coecuaciones
Variedades y covariedades
COECUACIONES
Definición
∗
Un conjunto de coecuaciones es un subautómata D ≤ 2A del
∗
autómata final (2A , τ ).
Definición
Diremos que el autómata (X, α, c) satisface D
(X, α, c) |= D ⇔ ∀x ∈ X, oc (x) ∈ D
Definimos:
(X, α) |= D ⇔ ∀c : X → 2, (X, α, c) |= D
15
Preliminares
Autómatas distinguidos
Ecuaciones y coecuaciones
Variedades y covariedades
COECUACIONES
Ejemplo
a
b
y
x
a
b
16
Preliminares
Autómatas distinguidos
Ecuaciones y coecuaciones
Variedades y covariedades
COECUACIONES
Ejemplo
a
b
y
x
a
b
Bajo la función de observabilidad tenemos:
oc (x) = (a∗ b)∗
oc (y) = (a∗ b)+
16
Preliminares
Autómatas distinguidos
Ecuaciones y coecuaciones
Variedades y covariedades
COECUACIONES
Ejemplo
a
b
y
x
a
b
Bajo la función de observabilidad tenemos:
oc (x) = (a∗ b)∗
oc (y) = (a∗ b)+
por lo que,
(X, α, c) |= {(a∗ b)∗ , (a∗ b)+ }
16
Preliminares
Autómatas distinguidos
Ecuaciones y coecuaciones
Variedades y covariedades
EQ(X, α), COEQ(X, α)
Definición
Definimos Eq(X, α) como el mayor conjunto de ecuaciones que
el autómata (X, α) satisface.
17
Preliminares
Autómatas distinguidos
Ecuaciones y coecuaciones
Variedades y covariedades
EQ(X, α), COEQ(X, α)
Definición
Definimos Eq(X, α) como el mayor conjunto de ecuaciones que
el autómata (X, α) satisface.
Definición
Definimos coEq(X, α) como el menor conjunto de coecuaciones
que el autómata (X, α) satisface.
17
Preliminares
Autómatas distinguidos
Ecuaciones y coecuaciones
Variedades y covariedades
EN UN EJEMPLO CONCRETO
Ejemplo
a
b
y
x
a
b
18
Preliminares
Autómatas distinguidos
Ecuaciones y coecuaciones
Variedades y covariedades
EN UN EJEMPLO CONCRETO
Ejemplo
a
b
y
x
a
b
Eq(X, α) = {aa = a, bb = b, ab = b, ba = a}
18
Preliminares
Autómatas distinguidos
Ecuaciones y coecuaciones
Variedades y covariedades
EN UN EJEMPLO CONCRETO
Ejemplo
[ε]
a
b
a
b
[b]
[a]
a
b
A∗ /Eq(X, α)
19
Preliminares
Autómatas distinguidos
Ecuaciones y coecuaciones
Variedades y covariedades
EN UN EJEMPLO CONCRETO
Ejemplo
a
b
(a∗ b)∗
(a∗ b)+
a
∅
a,b
b
a
a,b
A∗
b
(b∗ a)∗
(b∗ a)+
a
b
coEq(X, α)
20
VARIEDADES Y COVARIEDADES
Preliminares
Autómatas distinguidos
Ecuaciones y coecuaciones
Variedades y covariedades
VARIEDADES
Definición
Para cada conjunto E de ecuaciones definimos la variedad VE
como
VE = {(X, α) | (X, α) |= E}
22
Preliminares
Autómatas distinguidos
Ecuaciones y coecuaciones
Variedades y covariedades
VARIEDADES
Definición
Para cada conjunto E de ecuaciones definimos la variedad VE
como
VE = {(X, α) | (X, α) |= E}
Proposición
Toda variedad VE está cerrada bajo la formación de subautómatas, imágenes homomorfas y productos.
22
Preliminares
Autómatas distinguidos
Ecuaciones y coecuaciones
Variedades y covariedades
COVARIEDADES
Definición
Para cada conjunto D de coecuaciones definimos la covariedad
CD como
CD = {(X, α) | (X, α) |= D}
23
Preliminares
Autómatas distinguidos
Ecuaciones y coecuaciones
Variedades y covariedades
COVARIEDADES
Definición
Para cada conjunto D de coecuaciones definimos la covariedad
CD como
CD = {(X, α) | (X, α) |= D}
Proposición
Toda covariedad CD está cerrada bajo la formación de subautómatas, imágenes homomorfas y coproductos.
23
Preliminares
Autómatas distinguidos
Ecuaciones y coecuaciones
Variedades y covariedades
LENGUAJES
Definición
Sea VE una variedad. Definimos la variedad de lenguajes L(VE )
como
∗
L(VE ) = {L ∈ 2A | hLi ∈ VE }
24
Preliminares
Autómatas distinguidos
Ecuaciones y coecuaciones
Variedades y covariedades
LENGUAJES
Definición
Sea VE una variedad. Definimos la variedad de lenguajes L(VE )
como
∗
L(VE ) = {L ∈ 2A | hLi ∈ VE }
Definición
Sea CD una covariedad. Definimos la covariedad de lenguajes
L(CD ) como
∗
L(CD ) = {L ∈ 2A | hLi ∈ CD }
24
Preliminares
Autómatas distinguidos
Ecuaciones y coecuaciones
Variedades y covariedades
DE ECUACIONES Y VARIEDADES
Teorema
Sea E un conjunto de ecuaciones.
Las siguientes afirmaciones son equivalentes:
25
Preliminares
Autómatas distinguidos
Ecuaciones y coecuaciones
Variedades y covariedades
DE ECUACIONES Y VARIEDADES
Teorema
Sea E un conjunto de ecuaciones.
Las siguientes afirmaciones son equivalentes:
i. E es una congruencia.
25
Preliminares
Autómatas distinguidos
Ecuaciones y coecuaciones
Variedades y covariedades
DE ECUACIONES Y VARIEDADES
Teorema
Sea E un conjunto de ecuaciones.
Las siguientes afirmaciones son equivalentes:
i. E es una congruencia.
ii. E = Eq(X, α) para algún autómata (X, α).
25
Preliminares
Autómatas distinguidos
Ecuaciones y coecuaciones
Variedades y covariedades
DE ECUACIONES Y VARIEDADES
Teorema
Sea E un conjunto de ecuaciones.
Las siguientes afirmaciones son equivalentes:
i. E es una congruencia.
ii. E = Eq(X, α) para algún autómata (X, α).
iii. (A∗ /E, [σ]) |= E.
25
Preliminares
Autómatas distinguidos
Ecuaciones y coecuaciones
Variedades y covariedades
DE ECUACIONES Y VARIEDADES
Teorema
Sea E un conjunto de ecuaciones.
Las siguientes afirmaciones son equivalentes:
i. E es una congruencia.
ii. E = Eq(X, α) para algún autómata (X, α).
iii. (A∗ /E, [σ]) |= E.
iv. Eq(A∗ /E, [σ]) = E.
25
Preliminares
Autómatas distinguidos
Ecuaciones y coecuaciones
Variedades y covariedades
EN UN EJEMPLO CONCRETO
Ejemplo
[ε]
a
b
a
b
[b]
[a]
a
b
A∗ /Eq(X, α)
26
Preliminares
Autómatas distinguidos
Ecuaciones y coecuaciones
Variedades y covariedades
DE COECUACIONES Y COVARIEDADES
Teorema
Sea D un conjunto de coecuaciones.
Las siguientes afirmaciones son equivalentes:
27
Preliminares
Autómatas distinguidos
Ecuaciones y coecuaciones
Variedades y covariedades
DE COECUACIONES Y COVARIEDADES
Teorema
Sea D un conjunto de coecuaciones.
Las siguientes afirmaciones son equivalentes:
i. D = coEq(X, α) para algún autómata (X, α).
27
Preliminares
Autómatas distinguidos
Ecuaciones y coecuaciones
Variedades y covariedades
DE COECUACIONES Y COVARIEDADES
Teorema
Sea D un conjunto de coecuaciones.
Las siguientes afirmaciones son equivalentes:
i. D = coEq(X, α) para algún autómata (X, α).
ii. (D, τ ) |= D.
27
Preliminares
Autómatas distinguidos
Ecuaciones y coecuaciones
Variedades y covariedades
DE COECUACIONES Y COVARIEDADES
Teorema
Sea D un conjunto de coecuaciones.
Las siguientes afirmaciones son equivalentes:
i. D = coEq(X, α) para algún autómata (X, α).
ii. (D, τ ) |= D.
iii. coEq(D, τ ) = D.
27
Preliminares
Autómatas distinguidos
Ecuaciones y coecuaciones
Variedades y covariedades
DE COECUACIONES Y COVARIEDADES
Teorema
Sea D un conjunto de coecuaciones.
Las siguientes afirmaciones son equivalentes:
i. D = coEq(X, α) para algún autómata (X, α).
ii. (D, τ ) |= D.
iii. coEq(D, τ ) = D.
iv. L(CD ) = D.
27
Preliminares
Autómatas distinguidos
Ecuaciones y coecuaciones
Variedades y covariedades
EN UN EJEMPLO CONCRETO
Ejemplo
a
b
(a∗ b)∗
(a∗ b)+
a
∅
a,b
b
a
a,b
A∗
b
(b∗ a)∗
(b∗ a)+
a
b
coEq(X, α)
28
Preliminares
Autómatas distinguidos
Ecuaciones y coecuaciones
Variedades y covariedades
BIBLIOGRAFÍA
S. Eilenberg,
Automata, languages and machines (Vol. A and B),
Pure and applied mathematics. Academic Press, 1974.
J. Rutten,
Universal coalgebra: a theory of systems,
Elsevier, Theoretical Computer Science, Amsterdam, 2000.
J. Rutten, A. Ballester-Bolinches, E. Cosme-Llópez
Varieties and covarieties of languages (preliminary version),
MFPS XXIX Proceedings, 2013.
D. Sangiorgi, J. Rutten,
Advanced Topics in Bisimulation and Coinduction,
Cambridge Tracts in Theoretical Computer Science, 2012.
29