System disruptions
There are recurring service disruptions on some of the search portals due to high traffic. We are working to resolve the issue, you may temporarily encounter an error message.
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Synchronization and Diversity of Solutions
University of Bergen, Norway.
University of Trier, Germany.
Stockholm University, Faculty of Social Sciences, Department of Computer and Systems Sciences. University of Bergen, Norway.ORCID iD: 0000-0001-7798-7446
University of Bergen, Norway; University of Trier, Germany.
Number of Authors: 42023 (English)In: Proceedings of the 37th AAAI Conference on Artificial Intelligence / [ed] Brian Williams, Yiling Chen, Jennifer Neville, Association for the Advancement of Artificial Intelligence , 2023, p. 11516-11524Conference paper, Published paper (Refereed)
Abstract [en]

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.

Place, publisher, year, edition, pages
Association for the Advancement of Artificial Intelligence , 2023. p. 11516-11524
Series
Proceedings of the annual AAAI Conference on Artificial Intelligence, ISSN 2159-5399, E-ISSN 2374-3468 ; 37(10)
Keywords [en]
MAS: Coordination and Collaboration, MAS: Multiagent Planning
National Category
Computer Sciences
Research subject
Computer and Systems Sciences
Identifiers
URN: urn:nbn:se:su:diva-225847DOI: 10.1609/AAAI.V37I10.26361ISBN: 978-1-57735-880-0 (electronic)OAI: oai:DiVA.org:su-225847DiVA, id: diva2:1830701
Conference
The Thirty-Seventh AAAI Conference on Artificial Intelligence, Washington, D.C., USA, February 7–14, 2023.
Available from: 2024-01-23 Created: 2024-01-23 Last updated: 2024-11-11Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full text

Authority records

De Oliveira Oliveira, Mateus

Search in DiVA

By author/editor
De Oliveira Oliveira, Mateus
By organisation
Department of Computer and Systems Sciences
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 129 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf