Autômato ponderado

Na ciência da computação teórica , e particularmente na teoria dos autômatos , um autômato finito ponderado é uma generalização dos autômatos finitos . Em um autômato finito usual, seja determinístico ou não determinístico , as transições ou setas trazem rótulos que são letras do alfabeto subjacente. Em um autômato ponderado, qualquer transição também carrega um certo peso. Esse peso pode ser interpretado como o custo para passar de um estado para outro quando a transição é feita.

Definição matemática

Deixe ser um meio-anel e deixe ser um alfabeto . $K$ $\ Sigma$

Um autômato ponderado com peso em é composto dos seguintes objetos: $K$

um conjunto finito de estados $Q$
uma função de transição com valores em , ${\ displaystyle \ mu: Q \ times \ Sigma \ times Q \ a K}$ $K$
uma função de peso de entrada , ${\ displaystyle \ lambda: Q \ to K}$
uma função de peso de saída . ${\ displaystyle \ theta: Q \ to K}$

Um caminho em um autômato ponderado é uma sequência

{\ displaystyle (q_ {0}, a_ {1}, q_ {1}, a_ {2}, \ ldots, a_ {n}, q_ {n}) \}

onde estão estados e são letras. A palavra é o rótulo do caminho e o elemento do meio-anel é seu peso . O peso é, portanto, o produto do peso de entrada do primeiro estado pelo produto dos pesos das transições, multiplicado pelo peso de saída do último estado. O peso de uma palavra no autômato é a soma dos pesos de todos os caminhos rotulados por . A função calculada pelo PLC é a função que associa seu peso a uma palavra. Também é escrito como uma série formal: ${\ displaystyle q_ {0}, \ ldots, q_ {n} \ in Q}$ ${\ displaystyle a_ {1}, \ ldots, a_ {n} \ in \ Sigma}$ ${\ displaystyle a_ {1} a_ {2} \ cdots a_ {n} \}$ ${\ displaystyle \ lambda (q_ {0}) \ mu (q_ {0}, a_ {1}, q_ {1}) \ cdots \ mu (q_ {n-1}, a_ {n}, q_ {n} ) \ theta (q_ {n})}$ ${\ displaystyle w = a_ {1} a_ {2} ... a_ {n} \ in \ Sigma ^ {*}}$ ${\ displaystyle \ pi (w)}$ $C$

{\ displaystyle \ sum _ {w \ in \ Sigma ^ {*}} \ pi (w) \, w}

Notação de matriz

A função calculada por um autômato ponderado é expressa simplesmente com uma notação de matriz. Para isso, consideramos que o conjunto de estados são inteiros de 1 a . A função de transição define, para qualquer letra , uma matriz de ordem por ${\ displaystyle Q = \ {1, \ ldots, n \}}$ $não$ $no$ ${\ displaystyle \ nu (a)}$ $não$

{\ displaystyle \ nu (a) _ {p, q} = \ mu (p, a, q)}

Estendemos a um morfismo de em matrizes de ordem n pela fórmula $\nu$ ${\ displaystyle \ Sigma ^ {*}}$

{\ displaystyle \ nu (a_ {1} a_ {2} \ cdots a_ {n}) = \ nu (a_ {1}) \ nu (a_ {2}) \ cdots \ nu (a_ {n})}

Considerando como um vetor linha e como um vetor coluna, o peso de uma palavra é então simplesmente $\ lambda$ $\ theta$ $C$

{\ displaystyle \ pi (w) = \ lambda \ nu (w) \ theta}

É por isso que também encontramos a definição de um autômato ponderado como um tripleto . ${\ displaystyle (\ lambda, \ nu, \ theta)}$

Um primeiro exemplo

O autômato oposto tem dois estados. É um autômato no anel de inteiros . A representação gráfica indica que o vetor de entrada é , o vetor de saída transposto é , e as duas matrizes de transição são: $\ mathbb {Z}$ ${\ displaystyle \ lambda = (1 \ 0)}$ ${\ displaystyle \ theta ^ {t} = (0 \ 1)}$

{\ displaystyle \ nu (a) = {\ begin {pmatrix} 1 e 1 \\ 0 & 1 \ end {pmatrix}}}

{\ displaystyle \ nu (b) = {\ begin {pmatrix} 1 e -1 \\ 0 & 1 \ end {pmatrix}}}

Um cálculo de matriz mostra que, para uma palavra composta de letras e letras , temos $C$ $p$ $no$ $q$ $b$

{\ displaystyle \ nu (w) = {\ begin {pmatrix} 1 & p-q \\ 0 & 1 \ end {pmatrix}}}

Os vetores de entrada e saída são selecionados com um coeficiente de índice (1,2) e, portanto, temos

{\ displaystyle \ pi (w) = pq}

para uma palavra composta de letras e letras . Palavras cujo peso é zero são, portanto, palavras que têm tanto de quanto de . Como linguagem formal, esta linguagem, como seu complemento, não são linguagens regulares. Isso mostra que os autômatos ponderados reconhecem objetos muito mais gerais. $C$ $p$ $no$ $q$ $b$ $no$ $b$

Outros exemplos

Meio anel de Boole . O caso mais simples é o meio-anel booleano composto de 0 e 1. Um autômato finito no sentido usual do termo pode ser visto como um autômato ponderado com valores em . Para isso, corrigimos: $B$ $B$

o peso de entrada de um estado é 1 se for inicial, 0 caso contrário,
o peso de um tripleto (p, a, q) é 1 ou 0 dependendo se é uma transição do autômato ou não,
o peso de saída de um estado é 1 se for final, 0 caso contrário.

Com esta correspondência, o peso de um caminho PLC ponderado é 1 exatamente quando o caminho é um caminho bem sucedido no PLC tradicional e 0 caso contrário, e o peso de uma palavra é 1 ou 0 dependendo se é aceita ou não pelo máquina.

Meio anel tropical . Outro exemplo frequentemente considerado é o meio-anel tropical , onde é o elemento neutro da adição representado por e 0 é o elemento neutro para a operação + desempenhando o papel da multiplicação. Para esta ponderação, o peso de um caminho é a soma dos pesos de seus rótulos, e o peso de uma palavra é o mínimo dos pesos de todos os caminhos rotulados por aquela palavra. ${\ displaystyle {\ mathcal {T}} = (\ mathbb {R} \ cup \ infty, \ min, +, \ infty, 0)}$ $\ infty$ $\ min$

Autômatos probabilísticos e autômatos quânticos . Eles também são autômatos ponderados. Em um autômato probabilístico, os pesos representam probabilidades, e as matrizes da representação devem ser estocásticas , em um autômato quântico as matrizes são unitárias .

Os autômatos Mealy e, mais geralmente, os transdutores acabados também podem ser vistos como autômatos ponderados. Os pesos são então as palavras produzidas pelos autômatos: mais precisamente, se for o alfabeto de saída, o conjunto de partes de , fornecido com a união e a concatenação, é um meio-anel. O peso de uma palavra é então formado a partir do conjunto de palavras de saída de todos os caminhos de um determinado rótulo. $\Delta$ ${\ displaystyle \ Delta ^ {*}}$

Um caso particular consiste em autômatos ponderados determinísticos que são semelhantes aos autômatos sequenciais.

Teorema de Kleene-Schützenberger

O teorema de Kleene-Schützenberger é uma extensão do teorema de Kleene para autômatos ponderados. O teorema afirma que uma série formal de variáveis não comutativas com coeficientes em um meio-anel é racional se e somente se for reconhecida por um autômato finito ponderado, cujos respectivos pesos dos rótulos são elementos desse meio-anel.

Pólya series

As séries formais racionais de variáveis não comutativas com coeficientes em um campo têm propriedades aritméticas notáveis ligadas à natureza aritmética de seus coeficientes.

Uma série com coeficientes em um campo K é chamada de série Pólya se seus coeficientes diferentes de zero estiverem contidos em um subgrupo finitamente gerado de K *.

Um teorema de Pólya de 1921 descreve essas séries racionais no caso de uma variável. Foi então generalizado por Benali Benzaghou em 1970 e Jean-Paul Bézivin em 1987, novamente para uma variável. O caso de várias variáveis foi descrito por Daniel Smertnig e Jason Bell. arXiv: 1906.07271 Diz o seguinte: Uma série é uma série de Pólya precisamente quando é reconhecida por um autômato de peso inequívoco.

Nota Histórica

Autômatos finitos ponderados, principalmente considerados como séries formais, foram introduzidos como uma generalização de linguagens formais por Marcel-Paul Schützenberger no início dos anos 1960. Uma exposição sistemática, na forma de uma generalização de autômatos usuais, foi apresentada no tratado por Samuel Eilenberg . Em particular, ele introduziu o termo “ - -autômato” para designar um autômato no alfabeto e com valores no meio-anel . Mais recentemente, o livro de Jacques Sakarovitch e o manual de Droste, Kuich e Vogler ampliaram o campo e também incluíram aplicações práticas. $K$ $\ Sigma$ $\ Sigma$ $K$

Conferência bienal

A cada dois anos, há uma conferência científica chamada Weighted Automata: Theory and Applications (abreviado como WATA ) dedicada aos autômatos ponderados. Em 2020, a conferência será realizada em Marselha.

Notas e referências

Sakarovich 2003 diferencia entre o produto que chama de rótulo ou resultado e o valor que chama de cálculo . Droste, Kuich e Vogler 2009 chamam apenas o peso do produto . ${\ displaystyle \ mu (q_ {0}, a_ {1}, q_ {1}) \ cdots \ mu (q_ {n-1}, a_ {n}, q_ {n})}$ ${\ displaystyle \ lambda (q_ {0}) \ mu (q_ {0}, a_ {1}, q_ {1}) \ cdots \ mu (q_ {n-1}, a_ {n}, q_ {n} ) \ theta (q_ {n})}$ ${\ displaystyle \ mu (q_ {0}, a_ {1}, q_ {1}) \ cdots \ mu (q_ {n-1}, a_ {n}, q_ {n})}$
Este é o autômato de Sakarovich 2009 , Exercício 2.15, página 437.
Peter Kostolányi , “ On deterministic weighted automata ”, Information Processing Letters , vol. 140,2018, p. 42-47 ( DOI 10.1016 / j.ipl.2018.08.005 ).
Para extensões e variações, consulte, por exemplo , Droste, Kuich e Vogler 2009 .
George Pólya , “ Arithmetische Eigenschaften der Reihenentwicklungen rationaler Funktionen. », J. Reine Angew. Matemática. , vol. 151,1921, p. 1-31.
Bénali Benzaghou, “ Álgebras de Hadamard ”, Bull. Soc. Matemática. França , vol. 98,1970, p. 209-252 ( ler online , acessado em 10 de dezembro de 2019 ).
Jean-Paul Bézivin, “ Sequências recorrentes lineares em característica diferente de zero ”, Bull. Soc. Matemática. França , vol. 115, n o 21987, p. 227-239 ( ler online , acessado em 10 de dezembro de 2019 ).
Jason Bell e Daniel Smertnig, " Noncommutative rational Pólya series ", Arxiv ,2019( arXiv 1906.07271 ).
Schützenberger 1961 .
Eilenberg 1974 .
Sakarovich 2003 .
Droste, Kuich e Vogler 2009 .
Site da conferência WATA 2020 .

Bibliografia

Olivier Carton , linguagens formais, computabilidade e complexidade ,2008[ detalhe da edição ] ( leia online )
Marcel-Paul Schützenberger, “ Sobre a definição de uma família de autômatos ”, Informação e Controle , vol. 4,1961, p. 245–270 ( leia online ).
Manfred Droste, Werner Kuich e Heiko Vogler (editores), Handbook of Weighted Automata , Springer-Verlag, coll. "Monografias em ciência da computação teórica",2009, xvii + 608 pág. ( ISBN 978-3-642-01491-8 , DOI 10,1007 / 978-3-642-01492-5 , zbMATH 1200,68001 , SUDOC 139029907 )
Samuel Eilenberg, Automata, Languages and Machines, vol. A , Academic Press,1974( ISBN 978-0-12-234001-7 )

Jacques Sakarovitch, Elementos da teoria dos autômatos , Vuibert,2003, 816 p. ( ISBN 978-2-7117-4807-5 )- Tradução para o inglês com correções: (en) Jacques Sakarovitch, Elements of Automata Theory , Cambridge, Cambridge University Press,2009, 758 p. ( ISBN 978-0-521-84425-3 )
(pt) John E. Hopcroft , Rajeev Motwani e Jeffrey D. Ullman , Introdução à Teoria dos Autômatos, Linguagens e Computação , Addison-Wesley ,2007, 3 e ed. ( ISBN 978-0-32146225-1 )
Laure Daviaud, “Containment and Equivalence of Weighted Automata: Probabilistic and Max-Plus Cases” , in Language and Automata Theory and Applications. LATA 2020 , Springer, Cham, col. "Lecture Notes in Computer Science" ( n S 12038),2020( ISSN 0302-9743 , DOI 10.1007 / 978-3-030-40608-0_2 ) , p. 17-32