Automi e linguaggi formali
Dominique Perrin
La teoriadegliautomi e dei linguaggi formali ha lo scopo di descrivere le proprietà delle successioni di simboli. Tali successioni si presentano in situazioni [...] ricerca, che si sviluppa in due direzioni, l'una riguardante l'estensione della teoriadegliautomi finiti a parole infinite, l'altra lo studio dei legami tra teoriadegliautomi e logica formale. In questo quadro, Büchi ha dimostrato che i linguaggi ...
Leggi Tutto
Insieme di linee, reali o ideali, che si intrecciano formando incroci e nodi e dando luogo a una struttura complessa. Più in particolare, infrastruttura tecnica per la distribuzione di un segnale (tipicamente [...] a vari criteri, le scelte più convenienti e il guadagno atteso.
Le r. di Petri, proposte in base alla teoriadegliautomi a stati finiti e, per es., usate per analisi e simulazione di sistemi di elaborazione e di produzione manifatturiera, riguardano ...
Leggi Tutto
(o computer, o elaboratore elettronico) Apparecchio o dispositivo utilizzato per l’elaborazione di dati e segnali.
Cenni storici
Le origini
Il desiderio di realizzare uno strumento in grado di compiere [...] ; la costruzione di schemi di organizzazione dei sistemi, di meccanismi esecutivi e di controllo; la teoria dei linguaggi formali e la teoriadegliautomi.
Calcolatori quantistici
Si tratta di c. il cui funzionamento è basato sui principi della ...
Leggi Tutto
Informatica
Giorgio Ausiello
Carlo Batini
Vittorio Frosini
(App. IV, ii, p. 189; V, ii, p. 704)
Mentre negli anni 1937-38 venivano pubblicati l'ultimo volume della Enciclopedia Italiana e l'App. I, [...] alquanto lontano dai reali elaboratori, esso è stato ed è tuttora molto utilizzato, sia nella teoriadegliautomi e dei linguaggi formali, sia nella teoriadegli algoritmi per la sua grande semplicità formale e perché, rispetto alla RAM, si presta ...
Leggi Tutto
Il termine complessità è oggi frequentemente usato, in campo scientifico, in contesti diversi. In quello dell'informatica, dell'analisi numerica e dell'ottimizzazione, corrisponde alla caratteristica quantitativa [...] proposito vanno ricordati i nomi di J. von Neumann, H. von Foerster, H. Atlan e I. Prigogine. Nella sua teoriadegliautomi auto-organizzatori von Neumann si è posto il problema della differenza tra macchine artificiali e 'macchine viventi'. Egli ha ...
Leggi Tutto
Il concetto di calcolo costituisce uno dei più importanti fondamenti teorici delle discipline informatiche. Così come nelle discipline meccaniche non si possono comprendere le caratteristiche dei motori [...] un impiegato di banca, mentre successivamente W.S. McCullock, W. Pitts e S.C. Kleene gettarono le fondamenta della teoriadegliautomi a stati finiti tentando di modellare il comportamento dei neuroni e delle reti neuronali. Anche se risalgono agli ...
Leggi Tutto
Disciplina che si occupa dello studio unitario dei processi riguardanti «la comunicazione e il controllo nell’animale e nella macchina» (secondo la definizione di N. Wiener, 1947): partendo dalle ipotesi [...] esse va esplicitamente menzionata l’identificazione fra la c. e la teoria dell’informazione, e fra la c. e lo studio del linguaggio (automi) che presentano caratteristiche di stabilità, adattamento e apprendimento simili a quelle degli esseri ...
Leggi Tutto
La grande scienza. Automi e linguaggi formali
Dominique Perrin
Automi e linguaggi formali
La teoriadegliautomi e dei linguaggi formali ha lo scopo di descrivere le proprietà delle successioni di simboli. [...] seconda 1. Il problema del calcolo della star-height di un linguaggio razionale è stato sollevato fin dagli albori della teoriadegliautomi e risolto, in linea di principio, da Kosaburo Hashiguchi (1987), il quale ha dimostrato che la star-height è ...
Leggi Tutto
Informatica teorica
Giorgio Ausiello
Con l'espressione informatica teorica ci si riferisce a un complesso di discipline scientifiche aventi per oggetto lo studio formale degli strumenti, dei metodi [...] reali calcolatori, esso è tuttora utilizzato per la sua grande semplicità sia nella teoriadegliautomi e dei linguaggi formali sia nella teoria della complessità di calcolo. Per caratterizzare la complessità di un problema è importante individuare ...
Leggi Tutto
rete di Petri
Mauro Cappelli
Strumento teorico per la modellazione di processi in un sistema distribuito a stati discreti. Proposte nel 1962 da Carl Adam Petri, le reti di Petri rappresentano una teoria [...] generale per i sistemi discreti paralleli e sono basate su un linguaggio che risulta essere una generalizzazione della teoriadegliautomi. Esse permettono di rappresentare la struttura del sistema come un grafo composto da due tipi di nodi (detti ...
Leggi Tutto
automa
autòma (ant. autòmato) s. m. [dal lat. automătus, gr. αὐτόματος, agg., «che si muove da sé»] (pl. autòmi, ant. autòmati). – 1. Macchina che riproduce i movimenti (e in genere anche l’aspetto esterno) dell’uomo e degli animali. Quindi,...
macchina
màcchina (ant. màchina) s. f. [dal lat. machĭna, che è dal gr. dorico μαχανά, attico μηχανή]. – 1. In senso storico e antropologico, qualsiasi dispositivo o apparecchio costruito collegando opportunamente due o più elementi in modo...