使用 Answer Set Programming 生成最短同步序列

MMDec, 2013

使用 Answer Set Programming 生成最短同步序列

Generating Shortest Synchronizing Sequences using Answer Set Programming

Canan Güniçen, Esra Erdem, Hüsnü Yenigün

TL;DR检查有限自动机同步序列是否存在和找到最短同步序列是多项式时间内可解的，但是找到最短同步序列问题被称为 NP-hard 问题。本文研究了与暴力算法和基于 SAT 的方法相比，应用 Answer Set Programming 解决该优化问题的有效性。

Abstract

For a finite state automaton, a synchronizing sequence is an input sequence that takes all the states to the same state. Checking the existence of a synchronizing sequence and finding a synchronizing sequence, if one exists, can be performed in polynomial time. However, the problem of finding a shortest synchronizing sequence is known to be NP-hard. In this

finite automata shortest synchronizing sequence asp optimization problem sat

发现论文，激发创造

并行机器调度中的字典序最小完工时间优化的 ASP 实现

该论文利用 Answer-Set Programming 解决具有序列依赖设置时间和发布日期的并行机器工业调度问题，并采用多次求解算法来提高解决效率和可靠性。

Dec, 2022

应用答案集编程进行模式挖掘

本文探讨使用 Answer Set Programming（ASP）这样的声明性语言来有效地解决序列模式挖掘的问题，提出了几种 ASP 实现序列模式挖掘任务的方法，即非增量和增量分辨率，并发现增量分辨率比非增量分辨率更有效，在序列模式挖掘方面具有潜在的应用。

Sep, 2014

基于答案集规划的求解器调度

本研究提出了一种使用 Answer Set Programming 自动确定精细的、非均匀且有序的求解器调度方案的方法，并且可以定制化地生成并行调度方案。

Jan, 2014

有限轨迹上的时间答案集编程

介绍了一种基于 Temporal Equilibrium Logic 的替代方法，用于有限 trace 的 Temporal Answer Set Programming，可实现多通 Answer Set Programming 系统，并结合时间运算符扩展输入语言，同时提供了时间建模语言。

Apr, 2018

修改最小同步词长度上限

研究确定性有限自动机中的同步（周期，重置，幻数，可定向）字，并将上限值从（n^3-n）/6 降至 n（7n^2+6n-16）/48，同时提出了一种用于找到带有限制上界的同步字的算法。

Apr, 2011

答案集编程的成就

本文介绍了一种应答集编程的方法论，该方法可以促进易于理解且可以证明正确的编码方案的设计。通过向正在形成的程序追加一个规则或一小组规则，并在其中包含一条陈述已经 “实现” 的注释，使我们能够以数学上精确的方式描述程序设计的细节。

Aug, 2016

ASP 编码在序列模式挖掘任务中的效率分析

本文介绍了使用 Answer Set Programming（ASP）挖掘顺序模式。我们借助 ASP 对背景知识进行模式挖掘，提出了两种嵌入表示中经典顺序模式挖掘任务的编码，并对各种类型的模式比较了这些编码的计算性能。结果表明，fill-gaps 策略在实际问题中的内存消耗较低。相较于约束编程方法（CPSM），我们的方案表现稳定。

Nov, 2017

基于答案集编程的多智能体路径规划中的路由与调度：初步报告

我们提出了一种在答案集编程（ASP）中进行路由和调度的替代方法，并在多智能体路径规划的背景下进行了探索。这种方法捕捉了时间流的部分顺序而不是与行动和谓词相关联的时间步骤，终止了对计划长度的固定上界的需求。这种避免的代价是（部分）时间轨迹必须是无环的，因为不能再区分相同行动或谓词的多次出现。虽然这种方法为建模路由提供了一个有趣的替代方案，但对于调度来说却没有替代方案，因为精细化的计时无法以可行的方式在 ASP 中表示。而部分顺序可以通过外部手段（例如无环性和差别约束）进行高效处理。我们对这个想法进行了形式化的详细阐述并提出了几种结果的 ASP 编码。最后，我们通过实证分析证明了它们的有效性。

Mar, 2024

通过动态规划计算答案集数量

该论文提出一种基于动态规划的 ASP (#ASP) 算法，以解决基于原子命题公式的可满足性问题 (#SAT)，该算法利用底层 ASP 程序的结构，实验结果表明该算法在与现有求解器的比较中很有前途。

Dec, 2016

基于答集编程的有界组合重新配置

我们提出了一种称为有界组合重新配置的方法，用于基于 Answer Set Programming（ASP）解决组合重新配置问题。我们设计和实现了有界组合重新配置，并提出了独立集重新配置问题的 ASP 编码，这是最研究的组合重新配置问题之一。通过考虑 CoRe Challenge 2022 的所有实例，我们进行了实证分析。

Jul, 2023