Generating Shortest Synchronizing Sequences using Answer Set Programming
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 work, the usefulness of Answer Set Programming to solve this optimization problem is investigated, in comparison with brute-force algorithms and SAT-based approaches. Keywords: finite automata, shortest synchronizing sequence, ASP
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Generating Explanations for Biomedical Queries
We introduce novel mathematical models and algorithms to generate (shortest or k different) explanations for biomedical queries, using answer set programming. We implement these algorithms and integrate them in BIOQUERY-…
Drug DiscoveryBounded Combinatorial Reconfiguration with Answer Set Programming
We develop an approach called bounded combinatorial reconfiguration for solving combinatorial reconfiguration problems based on Answer Set Programming (ASP). The general task is to study the solution spaces of source com…
Bound Founded Answer Set Programming
Answer Set Programming (ASP) is a powerful modelling formalism that is very efficient in solving combinatorial problems. ASP solvers implement the stable model semantics that eliminates circular derivations between Boole…
A linear bound on the k-rendezvous time for primitive sets of NZ matrices
A set of nonnegative matrices is called primitive if there exists a product of these matrices that is entrywise positive. Motivated by recent results relating synchronizing automata and primitive sets, we study the lengt…
Anytime Computation of Cautious Consequences in Answer Set Programming
Query answering in Answer Set Programming (ASP) is usually solved by computing (a subset of) the cautious consequences of a logic program. This task is computationally very hard, and there are programs for which computin…