Answer set programming (original) (raw)
L'answer set programming (ASP) è una forma di programmazione logica di tipo dichiarativo utilizzato per problemi di ricerca complessi (in primis NP-difficili), basata sulla semantica del modello stabile (o answer set). In ASP i problemi di ricerca sono ridotti al calcolo di modelli stabili; per generare tali modelli vengono utilizzati programmi appositi noti come answer set solvers. Il linguaggio tipico di questo modello di programmazione è l'Answer Set Programming in Logic, sottoinsieme del Prolog, ed è impiegato in particolare per risolvere problemi di pianificazione (planning) e rappresentazione della conoscenza.
| Property | Value |
|---|---|
| dbo:abstract | Answer set programming (ASP) is a form of declarative programming oriented towards difficult (primarily NP-hard) search problems. It is based on the stable model (answer set) semantics of logic programming. In ASP, search problems are reduced to computing stable models, and answer set solvers—programs for generating stable models—are used to perform search. The computational process employed in the design of many answer set solvers is an enhancement of the DPLL algorithm and, in principle, it always terminates (unlike Prolog query evaluation, which may lead to an infinite loop). In a more general sense, ASP includes all applications of answer sets to knowledge representation and the use of Prolog-style query evaluation for solving problems arising in these applications. (en) La programación de conjuntos de respuestas (ASP) es una forma de programación declarativa orientada a problemas de búsqueda difíciles (principalmente NP-hard ). Se basa en la semántica del (conjunto de respuestas) de la programación lógica. En ASP, los problemas de búsqueda se reducen a la computación de modelos estables y los solucionadores de conjuntos de respuestas (programas para generar modelos estables) se utilizan para realizar búsquedas. El proceso computacional empleado en el diseño de muchos solucionadores de conjuntos de respuestas es una mejora del algoritmo DPLL y, en principio, siempre termina (a diferencia de la evaluación de consultas Prolog, que puede conducir a un bucle infinito). En un sentido más general, ASP incluye todas las aplicaciones de conjuntos de respuestas a la representación del conocimiento y el uso de la evaluación de consultas de estilo Prolog para resolver los problemas que surgen en estas aplicaciones. (es) L’answer set programming (ASP) est une forme de programmation déclarative adaptée aux problèmes de recherche combinatoires (par exemple, sudoku et coloration de graphes). Dans le contexte de la programmation logique, cette approche distingue deux types de négation — la négation par manque d'information, dite négation par défaut, et la négation forte ou négation logique. La négation par défaut permet de raisonner en l'absence d'information et rend l'ASP non monotone. L'exemple suivant, illustre le fonctionnement de la négation par défaut: * Si « X est un oiseau » mais pas « X est une autruche » alors « X vole » * « Titi est un oiseau » On peut déduire de ce programme le fait « Titi vole ». En effet, ici nous n'avons aucune information qui nous indique que Titi est une autruche. Cependant, si nous avions les informations «Lola est un oiseau et une autruche », alors nous ne pouvons pas déduire que Lola vole. La négation forte quant à elle demande une preuve qu'un fait est faux. Dans cet exemple, il faudrait donc prouver que Titi n'est pas une autruche pour en déduire qu'il vole. En ASP, la résolution de problème se réduit à calculer des modèles stables, c'est-à-dire où la négation par défaut produit des modèles logiquement consistants. Dans un sens plus général, ASP inclut des techniques de représentation des connaissances et l’évaluation de requêtes dans le style Prolog, pour résoudre les problèmes qui se posent dans ces applications. ASP permet de décider les problèmes dans NP et plus généralement les problèmes de la classe NPNP (voir hiérarchie polynomiale, l'existence d'un modèle stable est NPNP-complet). (fr) Programação de Conjunto de Resposta (ASP, da expressão em inglês Answer set programming) é uma forma de programação declarativa orientada a difíceis (principalmente NP-difícil). É baseado na semântica de modelo estável (conjunto de resposta) da . Em ASP, problemas de busca são reduzidos a modelos estáticos de computação, e solucionadores de conjunto de respostas - programas que geram modelos estáveis - são usados para realizar a busca. O processo computacional empregado no design de muitos solucionadores de conjuntos de respostas é uma melhora no algoritmo DPLL e, em princípio, sempre termina (diferentemente do processo de avaliação de consulta Prolog, que pode terminar em um laço infinito). Em um sentido mais geral, ASP inclui aplicações de conjunto de respostas para representação de conhecimento e o uso da avaliação de consultas no estilo Prolog para resolver problemas decorrentes das aplicações. (pt) L'answer set programming (ASP) è una forma di programmazione logica di tipo dichiarativo utilizzato per problemi di ricerca complessi (in primis NP-difficili), basata sulla semantica del modello stabile (o answer set). In ASP i problemi di ricerca sono ridotti al calcolo di modelli stabili; per generare tali modelli vengono utilizzati programmi appositi noti come answer set solvers. Il linguaggio tipico di questo modello di programmazione è l'Answer Set Programming in Logic, sottoinsieme del Prolog, ed è impiegato in particolare per risolvere problemi di pianificazione (planning) e rappresentazione della conoscenza. (it) Программирование наборов ответов (англ. Answer set programming, ASP) — форма декларативного программирования, ориентированная на сложные (в основном NP-трудные) задачи поиска, основывающееся на свойствах стабильной семантики логического программирования. Задача поиска — вычисление устойчивой модели и наборов решателей (англ. answer set solvers) — программ для генерации устойчивых моделей, которые используются для поиска. Вычислительный процесс, включённый в конструкцию набора решателей, — это надстройка над DPLL-алгоритмом, который всегда конечен (в отличие от оценки запроса в Прологе, которая может привести к бесконечному циклу). В более общем смысле техника включает все приложения из наборов ответов для представления знаний и использует оценки запросов в стиле Prolog для решения проблем, возникающих в этих наборах. (ru) Програмування наборами відповідей (англ. Answer set programming, ASP) — це форма декларативного програмування, орієнтованого на складні (насамперед, NP-складні) задачі пошуку. Воно засноване на стійкій моделі семантики логічного програмування. В ASP, задача пошуку зводиться до обчислювання стійкої моделі і наборів вирішувачів (англ. answer set solvers) — програм для генерування стійких моделей, що використовуються для пошуку. Обчислювальний процес, включений в конструкцію набору вирішувачів — є посиленням DPLL алгоритму, який завжди є скінченним (на відміну від оцінки запиту в Prolog, що може призвести до нескінченного циклу). Взагалі, ASP включає всі додатки з наборів відповідей для представлення знань та використання оцінки запитів, типу Prolog для вирішення задач, що виникають у цих додатках. (uk) 回答集编程是语法上类似传统逻辑编程而语义上密切于非单调逻辑的一种声明式编程。在传统逻辑编程和回答集编程之间的主要区别是如何表示否定为失败。在传统逻辑编程中，否定为失败指示推导失败；在回答集编程中，它指示一个文字的一致性。 (zh) |
| dbo:wikiPageExternalLink | http://www.cs.kuleuven.be/~dtai/events/ASP-competition/index.shtml http://www.cs.uky.edu/ai/pbmodels/ http://www.cs.uni-potsdam.de/clasp/ http://www.dbai.tuwien.ac.at/proj/dlv/ http://www.info.univ-angers.fr/pub/claire/asperix/ http://www.kr.tuwien.ac.at/staff/tkren/deb.html http://www.mat.unical.it/dlv-complex/ http://www.nku.edu/~wardj1/Research/smodels_cc.html http://www.tcs.hut.fi/Software/smodels/ https://potassco.org/ https://www.mat.unical.it/aspcomp2013/files/ASP-CORE-2.03c.pdf http://www.cs.utexas.edu/users/tag/cmodels/ http://www.cs.utexas.edu/users/tag/sup/ http://www.cs.uni-potsdam.de/nomore/ http://www.cs.uni-potsdam.de/platypus/ http://www.mat.unical.it/aspcomp2011/ http://www.mat.unical.it/aspcomp2013 http://www.tcs.hut.fi/Software/gnt/ http://www.tcs.hut.fi/Software/smodels/lparse.ps https://github.com/MatthiasNickles/diff-SAT/ https://web.archive.org/web/20080223132705/http:/asparagus.cs.uni-potsdam.de/contest/ https://web.archive.org/web/20110717180541/http:/assat.cs.ust.hk/ |
| dbo:wikiPageID | 2386211 (xsd:integer) |
| dbo:wikiPageLength | 26136 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1120931805 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Programming_paradigm dbr:Prolog dbr:Propositional_formula dbr:Natural_language_processing dbr:Parsing dbr:Declarative_programming dbr:Resolution_(logic) dbr:DLV dbr:DPLL_algorithm dbr:Default_logic dbr:Infinite_loop dbr:Coinduction dbr:GPL dbr:Graph_(discrete_mathematics) dbr:Graph_coloring dbr:NP-hard dbr:Linux dbr:MacOS dbr:Clique_(graph_theory) dbr:Path_(graph_theory) dbr:Action_language dbr:Logic_programming dbr:Non-monotonic_logic dbr:Directed_graph dbr:Symbol_grounding dbr:Knowledge_representation dbr:Backtracking dbr:Boolean_SAT_solver dbc:Logic_programming dbr:Java_virtual_machine dbr:Trial_and_error dbr:Automated_planning_and_scheduling dbr:Solaris_(operating_system) dbr:Freeware dbr:Microsoft_Windows dbr:Search_algorithm dbr:MIT_License dbr:Stable_model_semantics dbr:Hamiltonian_cycle dbr:Product_configuration dbr:Excluded_middle dbr:Pseudo-boolean |
| dbp:wikiPageUsesTemplate | dbt:Programming_paradigms dbt:Okay dbt:Distinguish dbt:No dbt:Reflist dbt:Yes |
| dct:subject | dbc:Logic_programming |
| gold:hypernym | dbr:Form |
| rdf:type | owl:Thing yago:Abstraction100002137 yago:GrammaticalRelation113796779 yago:Inflection113803782 yago:LinguisticRelation113797142 yago:Paradigm113804375 yago:Relation100031921 yago:WikicatProgrammingParadigms |
| rdfs:comment | L'answer set programming (ASP) è una forma di programmazione logica di tipo dichiarativo utilizzato per problemi di ricerca complessi (in primis NP-difficili), basata sulla semantica del modello stabile (o answer set). In ASP i problemi di ricerca sono ridotti al calcolo di modelli stabili; per generare tali modelli vengono utilizzati programmi appositi noti come answer set solvers. Il linguaggio tipico di questo modello di programmazione è l'Answer Set Programming in Logic, sottoinsieme del Prolog, ed è impiegato in particolare per risolvere problemi di pianificazione (planning) e rappresentazione della conoscenza. (it) 回答集编程是语法上类似传统逻辑编程而语义上密切于非单调逻辑的一种声明式编程。在传统逻辑编程和回答集编程之间的主要区别是如何表示否定为失败。在传统逻辑编程中，否定为失败指示推导失败；在回答集编程中，它指示一个文字的一致性。 (zh) Answer set programming (ASP) is a form of declarative programming oriented towards difficult (primarily NP-hard) search problems. It is based on the stable model (answer set) semantics of logic programming. In ASP, search problems are reduced to computing stable models, and answer set solvers—programs for generating stable models—are used to perform search. The computational process employed in the design of many answer set solvers is an enhancement of the DPLL algorithm and, in principle, it always terminates (unlike Prolog query evaluation, which may lead to an infinite loop). (en) La programación de conjuntos de respuestas (ASP) es una forma de programación declarativa orientada a problemas de búsqueda difíciles (principalmente NP-hard ). Se basa en la semántica del (conjunto de respuestas) de la programación lógica. En ASP, los problemas de búsqueda se reducen a la computación de modelos estables y los solucionadores de conjuntos de respuestas (programas para generar modelos estables) se utilizan para realizar búsquedas. El proceso computacional empleado en el diseño de muchos solucionadores de conjuntos de respuestas es una mejora del algoritmo DPLL y, en principio, siempre termina (a diferencia de la evaluación de consultas Prolog, que puede conducir a un bucle infinito). (es) L’answer set programming (ASP) est une forme de programmation déclarative adaptée aux problèmes de recherche combinatoires (par exemple, sudoku et coloration de graphes). Dans le contexte de la programmation logique, cette approche distingue deux types de négation — la négation par manque d'information, dite négation par défaut, et la négation forte ou négation logique. La négation par défaut permet de raisonner en l'absence d'information et rend l'ASP non monotone. L'exemple suivant, illustre le fonctionnement de la négation par défaut: (fr) Programação de Conjunto de Resposta (ASP, da expressão em inglês Answer set programming) é uma forma de programação declarativa orientada a difíceis (principalmente NP-difícil). É baseado na semântica de modelo estável (conjunto de resposta) da . Em ASP, problemas de busca são reduzidos a modelos estáticos de computação, e solucionadores de conjunto de respostas - programas que geram modelos estáveis - são usados para realizar a busca. O processo computacional empregado no design de muitos solucionadores de conjuntos de respostas é uma melhora no algoritmo DPLL e, em princípio, sempre termina (diferentemente do processo de avaliação de consulta Prolog, que pode terminar em um laço infinito). (pt) Программирование наборов ответов (англ. Answer set programming, ASP) — форма декларативного программирования, ориентированная на сложные (в основном NP-трудные) задачи поиска, основывающееся на свойствах стабильной семантики логического программирования. Задача поиска — вычисление устойчивой модели и наборов решателей (англ. answer set solvers) — программ для генерации устойчивых моделей, которые используются для поиска. Вычислительный процесс, включённый в конструкцию набора решателей, — это надстройка над DPLL-алгоритмом, который всегда конечен (в отличие от оценки запроса в Прологе, которая может привести к бесконечному циклу). (ru) Програмування наборами відповідей (англ. Answer set programming, ASP) — це форма декларативного програмування, орієнтованого на складні (насамперед, NP-складні) задачі пошуку. Воно засноване на стійкій моделі семантики логічного програмування. В ASP, задача пошуку зводиться до обчислювання стійкої моделі і наборів вирішувачів (англ. answer set solvers) — програм для генерування стійких моделей, що використовуються для пошуку. Обчислювальний процес, включений в конструкцію набору вирішувачів — є посиленням DPLL алгоритму, який завжди є скінченним (на відміну від оцінки запиту в Prolog, що може призвести до нескінченного циклу). (uk) |
| rdfs:label | Answer set programming (en) Programación de conjuntos de respuestas (es) Answer set programming (fr) Answer set programming (it) Programação de conjunto de resposta (pt) Программирование наборов ответов (ru) 回答集编程 (zh) Програмування наборами відповідей (uk) |
| owl:differentFrom | dbr:Active_Server_Pages |
| owl:sameAs | freebase:Answer set programming yago-res:Answer set programming wikidata:Answer set programming dbpedia-es:Answer set programming dbpedia-fa:Answer set programming dbpedia-fr:Answer set programming dbpedia-it:Answer set programming dbpedia-pt:Answer set programming dbpedia-ru:Answer set programming dbpedia-sr:Answer set programming dbpedia-uk:Answer set programming dbpedia-zh:Answer set programming https://global.dbpedia.org/id/2eck1 |
| prov:wasDerivedFrom | wikipedia-en:Answer_set_programming?oldid=1120931805&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Answer_set_programming |
| is dbo:wikiPageDisambiguates of | dbr:ASP |
| is dbo:wikiPageRedirects of | dbr:Answer_Set_Programming dbr:Disjunctive_logic_programming dbr:Lparse dbr:AnsProlog dbr:Answer-set_programming dbr:Answer_set_program |
| is dbo:wikiPageWikiLink of | dbr:Prolog dbr:Negation_as_failure dbr:Probabilistic_programming dbr:Algorithm_selection dbr:DLV dbr:Default_logic dbr:Answer_Set_Programming dbr:Glossary_of_artificial_intelligence dbr:Glossary_of_computer_science dbr:Constraint_satisfaction_problem dbr:Activity_recognition dbr:GOAL_agent_programming_language dbr:Logic_programming dbr:Datalog dbr:Nicola_Leone dbr:Frame_problem dbr:Knowledge-based_configuration dbr:Rule_Interchange_Format dbr:ASP dbr:Abductive_logic_programming dbr:B-Prolog dbr:Marius_Lindauer dbr:Satisfiability_modulo_theories dbr:Superoptimization dbr:Stable_model_semantics dbr:Outline_of_computer_programming dbr:Disjunctive_logic_programming dbr:Lparse dbr:AnsProlog dbr:Answer-set_programming dbr:Answer_set_program |
| is foaf:primaryTopic of | wikipedia-en:Answer_set_programming |