Synchronization and Diversity of Solutions
Authors: Emmanuel Arrighi, Henning Fernau, Mateus de Oliveira Oliveira, Petra Wolf
AAAI 2023 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this work, we study this problem within the framework of diversity of solutions... 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... The most central problem in the field of synchronization is the one to determine whether a given DFA has a synchronizing word. Note that this problem can be decided in polynomial time (Starke 1966). Nevertheless, in several applications, one is interested in finding a synchronizing word satisfying certain additional constraints (Fernau et al. 2019; Wolf 2020; T urker and Yenig un 2015). Here, the complexity landscape of the problem changes drastically: even the problem of determining the existence of a synchronizing word satisfying certain additional regularity constraints is NP-hard. |
| Researcher Affiliation | Academia | Emmanuel Arrighi1, Henning Fernau2, Mateus de Oliveira Oliveira1,3, Petra Wolf 1,2 1 University of Bergen, Bergen, Norway 2 University of Trier, Trier, Germany 3 Stockholm University, Stockholm, Sweden |
| Pseudocode | No | The paper describes algorithms and their complexities but does not include structured pseudocode or algorithm blocks. |
| Open Source Code | No | In the full version of this work (see https://doi.org/10.5281/zenodo.7384348), we discuss applications of our main results to several subdomains of artificial intelligence, such as multi-agent systems, robotics, secret sharing, and others. |
| Open Datasets | No | The paper is theoretical and focuses on algorithm design and complexity analysis for problems in automata theory and conformant planning. It does not involve empirical studies with datasets, training, or testing. |
| Dataset Splits | No | The paper is theoretical and does not involve empirical validation with dataset splits like training, validation, or test sets. |
| Hardware Specification | No | The paper is theoretical and does not discuss hardware specifications used for running experiments. |
| Software Dependencies | No | The paper is theoretical and does not mention specific software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and does not describe an experimental setup with specific hyperparameters or system-level training settings. |