Sökning: onr:"swepub:oai:DiVA.org:su-225847" >
Synchronization and...
Synchronization and Diversity of Solutions
-
- Arrighi, Emmanuel (författare)
- University of Bergen
-
- Fernau, Henning (författare)
- University of Trier
-
- De Oliveira Oliveira, Mateus (författare)
- Stockholms universitet,Institutionen för data- och systemvetenskap,University of Bergen
-
visa fler...
-
- Wolf, Petra (författare)
- University of Bergen; University of Trier
-
visa färre...
-
(creator_code:org_t)
- 2023
- 2023
- Engelska.
-
Ingår i: Thirty-Seventh AAAI Conference on Artificial Intelligence. - 9781577358800 ; , s. 11516-11524
- Relaterad länk:
-
https://urn.kb.se/re...
-
visa fler...
-
https://doi.org/10.1...
-
visa färre...
Abstract
Ämnesord
Stäng
- A central computational problem in the realm of automata theory is the problem of determining whether a finite automaton A has a synchronizing word. This problem has found applications in a variety of subfields of artificial intelligence, including planning, robotics, and multi-agent systems. In this work, we study this problem within the framework of diversity of solutions, an up-and-coming trend in the field of artificial intelligence where the goal is to compute a set of solutions that are sufficiently distinct from one another. We define a notion of diversity of solutions that is suitable for contexts were solutions are strings that may have distinct lengths. Using our notion of diversity, we show that for each fixed r ∈ N, each fixed finite automaton A, and each finite automaton B given at the input, the problem of determining the existence of a diverse set {w1,w2, . . . ,wr} ⊆ L(B) of words that are synchronizing for A can be solved in polynomial time. Finally, we generalize this result to the realm of conformant planning, where the goal is to devise plans that achieve a goal irrespectively of initial conditions and of nondeterminism that may occur during their execution.
Ämnesord
- NATURVETENSKAP -- Data- och informationsvetenskap -- Datavetenskap (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences -- Computer Sciences (hsv//eng)
Nyckelord
- MAS: Coordination and Collaboration
- MAS: Multiagent Planning
- data- och systemvetenskap
- Computer and Systems Sciences
Publikations- och innehållstyp
- ref (ämneskategori)
- kon (ämneskategori)
Hitta via bibliotek
Till lärosätets databas