Automa in viaggio

Un PLC che viaggia tra gli alberi , chiamato PLC journeying abbreviato ( automa inglese che cammina sugli alberi (TWA)) è una variante degli automi finiti che opera sugli alberi piuttosto che sulle parole . Il concetto era già stato definito da Aho e Ullman nel 1971.

Questo articolo tratta degli automi in viaggio. Gli automi degli alberi (ascendenti o discendenti) sono un'altra classe di automi e riconoscono l'albero dei linguaggi regolari .

Descrizione informale

Gli alberi qui considerati sono considerati binari ed etichettati con simboli di un alfabeto fisso Σ.

Un automa che attraversa A è un automa finito che attraversa un albero in sequenza. Inizia alla radice e finisce alla radice. In un dato momento, l'automa A "visita" un nodo v e si trova in un certo stato. A seconda dello stato, dell'etichetta del nodo v e del tipo di nodo (è la radice, un figlio sinistro o destro o è una foglia?), L'automa A cambia stato e si sposta sul genitore di v o su uno di i suoi figli. L'automa accetta un dato albero se finisce in uno stato finale alla radice. Per quanto riguarda gli automi a parole, un automa viaggiante può o non può essere deterministico.

Definizione

Un automa viaggiante (non deterministico) A = ( Q , Σ, I , F , R , δ) è composto dai seguenti dati:

Q è un insieme finito di stati,
Σ è un alfabeto,
I , F e R sono sottoinsiemi di stati, rispettivamente gli stati iniziale, di accettazione e di rifiuto
T è l'insieme di "tipi" disponibili: { nodo interno , foglia } × { radice , figlio sinistro , figlio destro }
δ ⊆ Q × T × Σ × { su , sinistra , destra } × Q è la relazione di transizione.

La relazione di transizione opera quindi in funzione dello stato, del tipo di nodo oltre che del simbolo letto sul nodo, decide il movimento e cambia stato.

Una configurazione PLC è una coppia formata ( q , v ) da uno stato e da un nodo. Il controller si avvia in una configurazione iniziale costituita da uno stato iniziale e dalla radice. Termina, se accetta l'albero, in una configurazione terminale formata da uno stato terminale e dalla radice.

Esempio

Ecco l'esempio di un automa in movimento che esegue l' algoritmo di attraversamento approfondito (DFS) su un dato albero. Il controller ha 3 stati, . L'automa parte dalla radice nello stato e scende nella sottostruttura sinistra. Quindi continua in modo ricorsivo: quando si entra in un nodo mentre si trova nello stato , significa che ha appena elaborato la sottostruttura sinistra di e procede all'elaborazione della sottostruttura destra di . Se entra in un nodo mentre si trova nello stato , significa che l'intera sottostruttura radice è stata visitata e si sposta sul genitore cambiando il suo stato in o , a seconda che si tratti di un figlio sinistro o destro. $A$ ${\ displaystyle Q = \ {q_ {0}, q _ {\ ell}, q_ {r} \}}$ ${\ displaystyle q_ {0}}$ $A$ $v$ ${\ displaystyle q _ {\ ell}}$ $v$ $v$ $A$ $v$ $q_ {r}$ $v$ $A$ $v$ ${\ displaystyle q _ {\ ell}}$ $q_ {r}$ $v$

Ecco altri esempi: Possiamo mostrare che l'insieme di alberi le cui foglie portano tutte lo stesso simbolo fisso a è riconoscibile da un automa in viaggio. Più in generale, l'insieme degli alberi, le cui foglie portano una parola in un linguaggio regolare fisso, può essere riconosciuto da un automa ambulante.

Proprietà

Alcune proprietà di base sono facili:

I linguaggi degli alberi riconosciuti dagli automi viaggianti sono chiusi per unione e per incrocio.
Un linguaggio ad albero riconosciuto da un automa che attraversa è riconosciuto anche da un automa ad albero (ma l'inclusione è rigorosa, vedi sotto).

A differenza degli automi degli alberi , gli automi viaggianti sono difficili da analizzare. Ecco alcune proprietà difficili da dimostrare:

Gli automi di attraversamento deterministici sono meno potenti degli automi di attraversamento non deterministici.
I linguaggi ad albero riconosciuti dagli automi dei cammini deterministici sono chiusi per complementazione (per gli automi non deterministici, il problema è aperto).
Tutti i linguaggi riconosciuti dagli automi che attraversano sono strettamente inclusi nella famiglia dei linguaggi riconosciuti dagli automi degli alberi.
Verifica se la lingua riconosciuta dagli automi in viaggio è vuota è EXPTIME-complete .

Appendici

Articolo correlato

Automa basato su token , un'estensione degli automi viaggianti.

Bibliografia

Alfred V. Aho e Jeffrey D. Ullman , " Traduzioni su una grammatica libera dal contesto ", Information and Control , vol. 19, n o 5,1971, p. 439–475 ( DOI 10.1016 / S0019-9958 (71) 90706-6 , leggi in linea )
Mikołaj Bojańczyk e Thomas Colcombet, " Gli automi che camminano sugli alberi non possono essere determinati ", Theoretical Computer Science , vol. 350 n ossa 2-3,2006, p. 164–173 ( DOI 10.1016 / j.tcs.2005.10.031 , leggi in linea )
Mikołaj Bojańczyk e Thomas Colcombet, " Gli automi che camminano sugli alberi non riconoscono tutti i linguaggi regolari ", SIAM Journal on Computing , vol. 38, n o 22008, p. 658–701 ( DOI 10.1137 / 050645427 , leggi in linea )
Mikołaj Bojańczyk, "Tree-walking automata" , in C. Martin-Vide, F. Otto e H. Fernau (editori), Teoria e applicazioni del linguaggio e degli automi, LATA 2008, Tarragona , Springer,2008( ISBN 9783540882817 ) , p. 1-2.
Anca Muscholl, Mathias Samuelides e Luc Segoufin, " Complementing deterministic tree-walking automata ", Information Processing Letters , vol. 99, n o 1,2006, p. 33-39.

Link esterno

Mikołaj Bojańczyk, " Automi che camminano sugli alberi " .