Separating words problem (original) (raw)
En la teoría computacional, el problema de separar palabras es el problema de encontrar el autómata finito determinista más pequeño que se comporta de manera diferente en dos cadenas dadas, lo que significa que acepta una de las dos cadenas y rechaza la otra. El tamaño que debe tener un autómata, en el peor de los casos, en función de la longitud de las cadenas de entrada es un problema abierto.
| Property | Value |
|---|---|
| dbo:abstract | En la teoría computacional, el problema de separar palabras es el problema de encontrar el autómata finito determinista más pequeño que se comporta de manera diferente en dos cadenas dadas, lo que significa que acepta una de las dos cadenas y rechaza la otra. El tamaño que debe tener un autómata, en el peor de los casos, en función de la longitud de las cadenas de entrada es un problema abierto. (es) In theoretical computer science, the separating words problem is the problem of finding the smallest deterministic finite automaton that behaves differently on two given strings, meaning that it accepts one of the two strings and rejects the other string. It is an open problem how large such an automaton must be, in the worst case, as a function of the length of the input strings. (en) |
| dbo:wikiPageID | 48936369 (xsd:integer) |
| dbo:wikiPageLength | 6839 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1124051712 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Deterministic_finite_automaton dbr:Modular_arithmetic dbr:Hamming_weight dbr:Parity_(mathematics) dbr:String_(computer_science) dbr:Theoretical_computer_science dbr:String_operations dbr:Open_problem dbr:Almost_all dbc:Unsolved_problems_in_computer_science dbc:Finite_automata dbc:Problems_on_strings dbr:Hamming_distance dbr:Jeffrey_Shallit dbr:Prime_number |
| dbp:wikiPageUsesTemplate | dbt:Harvtxt dbt:Math dbt:Mvar dbt:Reflist dbt:Unsolved |
| dct:subject | dbc:Unsolved_problems_in_computer_science dbc:Finite_automata dbc:Problems_on_strings |
| gold:hypernym | dbr:Problem |
| rdf:type | dbo:Disease |
| rdfs:comment | En la teoría computacional, el problema de separar palabras es el problema de encontrar el autómata finito determinista más pequeño que se comporta de manera diferente en dos cadenas dadas, lo que significa que acepta una de las dos cadenas y rechaza la otra. El tamaño que debe tener un autómata, en el peor de los casos, en función de la longitud de las cadenas de entrada es un problema abierto. (es) In theoretical computer science, the separating words problem is the problem of finding the smallest deterministic finite automaton that behaves differently on two given strings, meaning that it accepts one of the two strings and rejects the other string. It is an open problem how large such an automaton must be, in the worst case, as a function of the length of the input strings. (en) |
| rdfs:label | Problema de separación de palabras (es) Separating words problem (en) |
| owl:sameAs | yago-res:Separating words problem wikidata:Separating words problem dbpedia-es:Separating words problem dbpedia-fa:Separating words problem https://global.dbpedia.org/id/2NrLu |
| prov:wasDerivedFrom | wikipedia-en:Separating_words_problem?oldid=1124051712&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Separating_words_problem |
| is dbo:wikiPageWikiLink of | dbr:Deterministic_finite_automaton dbr:List_of_unsolved_problems_in_computer_science |
| is foaf:primaryTopic of | wikipedia-en:Separating_words_problem |