Reachability problem (original) (raw)
Le problème d'accessibilité (aussi appelé le problème d'atteignabilité) est, en informatique, le problème algorithmique qui consiste à déterminer si, dans un système, une situation finale est accessible/atteignable depuis une situation initiale. Le problème d'accessibilité a été étudié dans les automates finis, les automates cellulaires, les automates temporisés, les systèmes infinis, etc.
| Property | Value |
|---|---|
| dbo:abstract | Reachability is a fundamental problem that appears in several different contexts: finite- and infinite-state concurrent systems, computational models like cellular automata and Petri nets, program analysis, discrete and continuous systems, time critical systems, hybrid systems, rewriting systems, probabilistic and parametric systems, and open systems modelled as games. In general the reachability problem can be formulated as follows: Given a computational (potentially infinite state) system with a set of allowed rules or transformations, decide whether a certain state of a system is reachable from a given initial state of the system. Variants of the reachability problem may result from additional constraints on the initial or final states, specific requirement for reachability paths as well as for iterative reachability or changing the questions into analysis of winning strategies in infinite games or unavoidability of some dynamics. Typically, for a fixed system description given in some form (reduction rules, systems of equations, logical formulas, etc.) a reachability problem consists of checking whether a given set of target states can be reached starting from a fixed set of initial states. The set of target states can be represented explicitly or via some implicit representation (e.g., a system of equations, a set of minimal elements with respect to some ordering on the states). Sophisticated quantitative and qualitative properties can often be reduced to basic reachability questions. Decidability and complexity boundaries, algorithmic solutions, and efficient heuristics are all important aspects to be considered in this context. Algorithmic solutions are often based on different combinations of exploration strategies, symbolic manipulations of sets of states, decomposition properties, or reduction to linear programming problems, and they often benefit from approximations, abstractions, accelerations and extrapolation heuristics. Ad hoc solutions as well as solutions based on general purpose constraint solvers and deduction engines are often combined in order to balance efficiency and flexibility. (en) Le problème d'accessibilité (aussi appelé le problème d'atteignabilité) est, en informatique, le problème algorithmique qui consiste à déterminer si, dans un système, une situation finale est accessible/atteignable depuis une situation initiale. Le problème d'accessibilité a été étudié dans les automates finis, les automates cellulaires, les automates temporisés, les systèmes infinis, etc. (fr) Alcançabilidade é um problema fundamental que aparece em diferentes contextos: sistemas concorrentes de variável de estado finito e infinito modelos computacionais como autómato celular e rede de Petri, análise de programas, sistemas discretos e contínuos, sistemas de tempo crítico, sistemas híbridos, sistema de redução, probabilístico e sistemas paramétricos, e sistemas abertos modelados como jogos. Em geral o problema da alcançabilidade pode ser formulado da seguinte forma: Dado um sistema computacional (potencialmente de estado infinito) com um conjunto de regras ou transformações permitidas, decida se um dado estado de um sistema é alcançável a partir de um dado estado inicial do sistema. Variantes do problema da alcançabilidade podem resultar de restrições adicionais em seus estados inicial ou final, requerimentos específicos de caminhos de alcançabilidade assim como de alcançabilidade iterativa ou mudando as questões analisadas de estratégias para vencer jogos infinitos ou inevitabilidade de algumas dinâmicas. Tipicamente, para um sistema fixo descritivo dado em alguma forma (regras de redução, sistemas de equações, fórmulas lógicas, etc.) um problema de alcançabilidade consiste em checar se um dado conjunto de estados alvos conseguem ser atingidos a partir de um conjunto fixo de estados iniciais. O conjunto de estados alvos podem ser representados explicitamente ou através de alguma representação implícita (e.g., um sistema de equações, um conjunto de elementos mínimos com respeito a uma ordem de estados). Propriedades quantitativas e qualitativas sofisticadas podem ser reduzidas a questões de alcançabilidade básicas. Decidibilidade e fronteiras complexas, soluções algorítmicas, e heurísticas eficientes são todos aspectos importantes para serem considerados neste contexto. Soluções algorítmicas são freqüentemente baseadas em uma combinação diferente de estratégias explorarias, manipulações simbólicas de conjuntos de estados, propriedades de decomposição, ou redução à problemas de programação linear, e freqüentemente se beneficiam de aproximações, abstrações, acelerações e heurísticas de extrapolação. Soluções ad hoc assim como soluções baseadas no uso geral de soluções com restrições e motores dedutíveis são muitas vezes combinados a fim de balancear eficiência e flexibilidade. (pt) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Probleme_accessibilite.png?width=300 |
| dbo:wikiPageID | 38878183 (xsd:integer) |
| dbo:wikiPageLength | 6469 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1070872773 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Probabilistic dbr:Open_system_(control_theory) dbr:Game_theory dbr:Model_checking dbr:Computational_model dbr:Parametric_equation dbr:Petri_net dbr:Planning dbr:System_of_equations dbr:Linear_programming dbr:Discrete_system dbr:Iteration dbr:Heuristics dbr:Hybrid_system dbr:State_variable dbc:Theory_of_computation dbr:Binary_decision_diagram dbr:Recursive_set dbr:Cellular_automata dbr:Program_analysis dbr:Workshop_on_Reachability_Problems dbr:Rewriting_system dbr:Concurrent_systems dbr:Constraint_solver dbr:File:Probleme_accessibilite.png |
| dbp:wikiPageUsesTemplate | dbt:Empty_section dbt:Full_citation_needed dbt:Reflist dbt:Short_description |
| dcterms:subject | dbc:Theory_of_computation |
| gold:hypernym | dbr:Problem |
| rdf:type | dbo:Disease |
| rdfs:comment | Le problème d'accessibilité (aussi appelé le problème d'atteignabilité) est, en informatique, le problème algorithmique qui consiste à déterminer si, dans un système, une situation finale est accessible/atteignable depuis une situation initiale. Le problème d'accessibilité a été étudié dans les automates finis, les automates cellulaires, les automates temporisés, les systèmes infinis, etc. (fr) Reachability is a fundamental problem that appears in several different contexts: finite- and infinite-state concurrent systems, computational models like cellular automata and Petri nets, program analysis, discrete and continuous systems, time critical systems, hybrid systems, rewriting systems, probabilistic and parametric systems, and open systems modelled as games. (en) Alcançabilidade é um problema fundamental que aparece em diferentes contextos: sistemas concorrentes de variável de estado finito e infinito modelos computacionais como autómato celular e rede de Petri, análise de programas, sistemas discretos e contínuos, sistemas de tempo crítico, sistemas híbridos, sistema de redução, probabilístico e sistemas paramétricos, e sistemas abertos modelados como jogos. Em geral o problema da alcançabilidade pode ser formulado da seguinte forma: (pt) |
| rdfs:label | Problème d'accessibilité (fr) Reachability problem (en) Problema da alcançabilidade (pt) |
| owl:sameAs | freebase:Reachability problem wikidata:Reachability problem dbpedia-bg:Reachability problem dbpedia-fr:Reachability problem dbpedia-pt:Reachability problem https://global.dbpedia.org/id/gR35 |
| prov:wasDerivedFrom | wikipedia-en:Reachability_problem?oldid=1070872773&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Probleme_accessibilite.png |
| foaf:isPrimaryTopicOf | wikipedia-en:Reachability_problem |
| is dbo:wikiPageWikiLink of | dbr:International_Conference_on_Reachability_Problems dbr:Petri_net dbr:Kalman_decomposition dbr:Word_problem_for_groups dbr:Reachability_analysis dbr:Timed_automaton |
| is foaf:primaryTopic of | wikipedia-en:Reachability_problem |
