| dbo:abstract
|
- Un autòmat finit acíclic determinista és un tipus d'autòmat finit (en anglès deterministic acyclic finite state automaton, DAFSA) és una estructura de dades que representa un conjunt de cadenes de caràcters i permet operacions de cerca i qüestions sobre si una cadena donada pertany al conjunt en un temps proporcional a la seva longitud. Existeixen algorismes per construir i mantenir aquest tipus d'autòmats mantenint-los de mida mínima. Un DAFSA és un cas especial d'autòmat finit reconeixedor que pren la forma de graf acíclic dirigit amb un sol vèrtex font (un vèrtex sense cap entrada), on cada aresta del graf està etiquetada amb una lletra o símbol, i per cada vèrtex te almenys una aresta per cada símbol o lletra possible. Les cadenes representades per un DAFSA estan formades pels símbols en els camins al graf des del vèrtex font fins a qualsevol vèrtex destí (un vèrtex sense cap sortida). De fet, un autòmat finit determinista és acíclic si i només si reconeix un conjunt finit de cadenes. (ca)
- In computer science, a deterministic acyclic finite state automaton (DAFSA),also called a directed acyclic word graph (DAWG; though that name also refers to a related data structure that functions as a suffix index)is a data structure that represents a set of strings, and allows for a query operation that tests whether a given string belongs to the set in time proportional to its length. Algorithms exist to construct and maintain such automata, while keeping them minimal. A DAFSA is a special case of a finite state recognizer that takes the form of a directed acyclic graph with a single source vertex (a vertex with no incoming edges), in which each edge of the graph is labeled by a letter or symbol, and in which each vertex has at most one outgoing edge for each possible letter or symbol. The strings represented by the DAFSA are formed by the symbols on paths in the graph from the source vertex to any sink vertex (a vertex with no outgoing edges). In fact, a deterministic finite state automaton is acyclic if and only if it recognizes a finite set of strings. (en)
- Em ciência da computação, um autômato finito determinístico acíclico (AFDA),também chamado de grafo orientado acíclico de palavras (GOAP; apesar desse nome também se referir a uma que funciona como um índice de sufixo)é uma estrutura de dados que representa um conjunto de cadeias de caracteres, e permite uma operação de consulta que testa se uma dada cadeia pertence ao conjunto em tempo proporcional ao seu comprimento. Algoritmos existem para criar e manter tais autômatos, enquanto os mantêm mínimo. Um AFDA é um caso especial de uma máquina de estados finitos que toma a forma de um grafo acíclico orientado com um único vértice fonte (um vértice que nenhuma aresta o têm como destino), em que cada aresta do grafo é rotulada por uma letra ou um símbolo, e em que cada vértice tem no máximo uma aresta que o têm como origem por símbolo. As sequências de caracteres representados pelo AFDA são formada pelos símbolos nos caminhos do grafo a partir do vértice fonte para o vértice sumidouro (ou poço) (um vértice que nenhuma aresta o têm como origem). De fato, um autômato finito determinístico é acíclico se, e somente se reconhece um conjunto finito de cadeias de caracteres. (pt)
|
| dbo:thumbnail
| |
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 7120 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| gold:hypernym
| |
| rdf:type
| |
| rdfs:comment
|
- Un autòmat finit acíclic determinista és un tipus d'autòmat finit (en anglès deterministic acyclic finite state automaton, DAFSA) és una estructura de dades que representa un conjunt de cadenes de caràcters i permet operacions de cerca i qüestions sobre si una cadena donada pertany al conjunt en un temps proporcional a la seva longitud. Existeixen algorismes per construir i mantenir aquest tipus d'autòmats mantenint-los de mida mínima. (ca)
- In computer science, a deterministic acyclic finite state automaton (DAFSA),also called a directed acyclic word graph (DAWG; though that name also refers to a related data structure that functions as a suffix index)is a data structure that represents a set of strings, and allows for a query operation that tests whether a given string belongs to the set in time proportional to its length. Algorithms exist to construct and maintain such automata, while keeping them minimal. (en)
- Em ciência da computação, um autômato finito determinístico acíclico (AFDA),também chamado de grafo orientado acíclico de palavras (GOAP; apesar desse nome também se referir a uma que funciona como um índice de sufixo)é uma estrutura de dados que representa um conjunto de cadeias de caracteres, e permite uma operação de consulta que testa se uma dada cadeia pertence ao conjunto em tempo proporcional ao seu comprimento. Algoritmos existem para criar e manter tais autômatos, enquanto os mantêm mínimo. (pt)
|
| rdfs:label
|
- Autòmat finit acíclic determinista (ca)
- Deterministic acyclic finite state automaton (en)
- Autômato finito determinístico acíclico (pt)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:depiction
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
