A Modal Logic for Joint Abilities of Structured Strategies with Bounded Complexity Article Swipe
Ronghua Jin
,
Yongmei Liu
,
Liping Xiong
·
YOU?
·
· 2025
· Open Access
·
· DOI: https://doi.org/10.1609/aaai.v39i14.33646
YOU?
·
· 2025
· Open Access
·
· DOI: https://doi.org/10.1609/aaai.v39i14.33646
Coordination and joint ability are important topics in representation and reasoning about multi-agent systems. The modal logic JAADL proposed by Liu et al. extends ATL with joint abilities, which enables reasoning about whether a coalition of agents can coordinate and achieve a goal without communication. However, like ATL, strategic abilities in JAADL are defined in terms of combinatorial strategies, which are functions from histories or states to actions. On the other hand, there has been research on reasoning about natural strategic abilities, where a natural strategy is formalized as a sequence of condition-action pairs, making it more human-friendly than combinatorial strategy. In this work, we propose SJAADL, a variation of JAADL where strategic abilities are defined in terms of structured strategies represented with LDL (linear dynamic logic) formulas, with bounded complexity. We use nondeterministic strategies since they are more expressive, natural and succinct than determinstic ones. We present syntax and semantics of SJAADL. We show that model checking SJAADL can be done in time quasi-polynomial with the model size, exponential with the formula size, and with the complexity bound of structured strategies, exponential in the memoryless case and double exponential in the memoryful case. Finally, we introduce the problem of synthesizing norms to achieve joint abilities, and give two algorithms for it.
Related Topics
Concepts
Metadata
- Type
- article
- Language
- en
- Landing Page
- https://doi.org/10.1609/aaai.v39i14.33646
- https://ojs.aaai.org/index.php/AAAI/article/download/33646/35801
- OA Status
- diamond
- Related Works
- 10
- OpenAlex ID
- https://openalex.org/W4409364899
All OpenAlex metadata
Raw OpenAlex JSON
- OpenAlex ID
-
https://openalex.org/W4409364899Canonical identifier for this work in OpenAlex
- DOI
-
https://doi.org/10.1609/aaai.v39i14.33646Digital Object Identifier
- Title
-
A Modal Logic for Joint Abilities of Structured Strategies with Bounded ComplexityWork title
- Type
-
articleOpenAlex work type
- Language
-
enPrimary language
- Publication year
-
2025Year of publication
- Publication date
-
2025-04-11Full publication date if available
- Authors
-
Ronghua Jin, Yongmei Liu, Liping XiongList of authors in order
- Landing page
-
https://doi.org/10.1609/aaai.v39i14.33646Publisher landing page
- PDF URL
-
https://ojs.aaai.org/index.php/AAAI/article/download/33646/35801Direct link to full text PDF
- Open access
-
YesWhether a free full text is available
- OA status
-
diamondOpen access status per OpenAlex
- OA URL
-
https://ojs.aaai.org/index.php/AAAI/article/download/33646/35801Direct OA link when available
- Concepts
-
Bounded function, Modal, Modal logic, Joint (building), Computer science, Mathematics, Theoretical computer science, Engineering, Structural engineering, Materials science, Mathematical analysis, Polymer chemistryTop concepts (fields/topics) attached by OpenAlex
- Cited by
-
0Total citation count in OpenAlex
- Related works (count)
-
10Other works algorithmically related by OpenAlex
Full payload
| id | https://openalex.org/W4409364899 |
|---|---|
| doi | https://doi.org/10.1609/aaai.v39i14.33646 |
| ids.doi | https://doi.org/10.1609/aaai.v39i14.33646 |
| ids.openalex | https://openalex.org/W4409364899 |
| fwci | 0.0 |
| type | article |
| title | A Modal Logic for Joint Abilities of Structured Strategies with Bounded Complexity |
| biblio.issue | 14 |
| biblio.volume | 39 |
| biblio.last_page | 15023 |
| biblio.first_page | 15014 |
| topics[0].id | https://openalex.org/T11010 |
| topics[0].field.id | https://openalex.org/fields/17 |
| topics[0].field.display_name | Computer Science |
| topics[0].score | 0.9472000002861023 |
| topics[0].domain.id | https://openalex.org/domains/3 |
| topics[0].domain.display_name | Physical Sciences |
| topics[0].subfield.id | https://openalex.org/subfields/1702 |
| topics[0].subfield.display_name | Artificial Intelligence |
| topics[0].display_name | Logic, Reasoning, and Knowledge |
| is_xpac | False |
| apc_list | |
| apc_paid | |
| concepts[0].id | https://openalex.org/C34388435 |
| concepts[0].level | 2 |
| concepts[0].score | 0.6259790658950806 |
| concepts[0].wikidata | https://www.wikidata.org/wiki/Q2267362 |
| concepts[0].display_name | Bounded function |
| concepts[1].id | https://openalex.org/C71139939 |
| concepts[1].level | 2 |
| concepts[1].score | 0.6256585717201233 |
| concepts[1].wikidata | https://www.wikidata.org/wiki/Q910194 |
| concepts[1].display_name | Modal |
| concepts[2].id | https://openalex.org/C27508121 |
| concepts[2].level | 3 |
| concepts[2].score | 0.6163129210472107 |
| concepts[2].wikidata | https://www.wikidata.org/wiki/Q210841 |
| concepts[2].display_name | Modal logic |
| concepts[3].id | https://openalex.org/C18555067 |
| concepts[3].level | 2 |
| concepts[3].score | 0.5731775760650635 |
| concepts[3].wikidata | https://www.wikidata.org/wiki/Q8375051 |
| concepts[3].display_name | Joint (building) |
| concepts[4].id | https://openalex.org/C41008148 |
| concepts[4].level | 0 |
| concepts[4].score | 0.48378488421440125 |
| concepts[4].wikidata | https://www.wikidata.org/wiki/Q21198 |
| concepts[4].display_name | Computer science |
| concepts[5].id | https://openalex.org/C33923547 |
| concepts[5].level | 0 |
| concepts[5].score | 0.35219308733940125 |
| concepts[5].wikidata | https://www.wikidata.org/wiki/Q395 |
| concepts[5].display_name | Mathematics |
| concepts[6].id | https://openalex.org/C80444323 |
| concepts[6].level | 1 |
| concepts[6].score | 0.33237558603286743 |
| concepts[6].wikidata | https://www.wikidata.org/wiki/Q2878974 |
| concepts[6].display_name | Theoretical computer science |
| concepts[7].id | https://openalex.org/C127413603 |
| concepts[7].level | 0 |
| concepts[7].score | 0.1810148060321808 |
| concepts[7].wikidata | https://www.wikidata.org/wiki/Q11023 |
| concepts[7].display_name | Engineering |
| concepts[8].id | https://openalex.org/C66938386 |
| concepts[8].level | 1 |
| concepts[8].score | 0.15130874514579773 |
| concepts[8].wikidata | https://www.wikidata.org/wiki/Q633538 |
| concepts[8].display_name | Structural engineering |
| concepts[9].id | https://openalex.org/C192562407 |
| concepts[9].level | 0 |
| concepts[9].score | 0.12515929341316223 |
| concepts[9].wikidata | https://www.wikidata.org/wiki/Q228736 |
| concepts[9].display_name | Materials science |
| concepts[10].id | https://openalex.org/C134306372 |
| concepts[10].level | 1 |
| concepts[10].score | 0.06845107674598694 |
| concepts[10].wikidata | https://www.wikidata.org/wiki/Q7754 |
| concepts[10].display_name | Mathematical analysis |
| concepts[11].id | https://openalex.org/C188027245 |
| concepts[11].level | 1 |
| concepts[11].score | 0.0 |
| concepts[11].wikidata | https://www.wikidata.org/wiki/Q750446 |
| concepts[11].display_name | Polymer chemistry |
| keywords[0].id | https://openalex.org/keywords/bounded-function |
| keywords[0].score | 0.6259790658950806 |
| keywords[0].display_name | Bounded function |
| keywords[1].id | https://openalex.org/keywords/modal |
| keywords[1].score | 0.6256585717201233 |
| keywords[1].display_name | Modal |
| keywords[2].id | https://openalex.org/keywords/modal-logic |
| keywords[2].score | 0.6163129210472107 |
| keywords[2].display_name | Modal logic |
| keywords[3].id | https://openalex.org/keywords/joint |
| keywords[3].score | 0.5731775760650635 |
| keywords[3].display_name | Joint (building) |
| keywords[4].id | https://openalex.org/keywords/computer-science |
| keywords[4].score | 0.48378488421440125 |
| keywords[4].display_name | Computer science |
| keywords[5].id | https://openalex.org/keywords/mathematics |
| keywords[5].score | 0.35219308733940125 |
| keywords[5].display_name | Mathematics |
| keywords[6].id | https://openalex.org/keywords/theoretical-computer-science |
| keywords[6].score | 0.33237558603286743 |
| keywords[6].display_name | Theoretical computer science |
| keywords[7].id | https://openalex.org/keywords/engineering |
| keywords[7].score | 0.1810148060321808 |
| keywords[7].display_name | Engineering |
| keywords[8].id | https://openalex.org/keywords/structural-engineering |
| keywords[8].score | 0.15130874514579773 |
| keywords[8].display_name | Structural engineering |
| keywords[9].id | https://openalex.org/keywords/materials-science |
| keywords[9].score | 0.12515929341316223 |
| keywords[9].display_name | Materials science |
| keywords[10].id | https://openalex.org/keywords/mathematical-analysis |
| keywords[10].score | 0.06845107674598694 |
| keywords[10].display_name | Mathematical analysis |
| language | en |
| locations[0].id | doi:10.1609/aaai.v39i14.33646 |
| locations[0].is_oa | True |
| locations[0].source.id | https://openalex.org/S4210191458 |
| locations[0].source.issn | 2159-5399, 2374-3468 |
| locations[0].source.type | conference |
| locations[0].source.is_oa | True |
| locations[0].source.issn_l | 2159-5399 |
| locations[0].source.is_core | False |
| locations[0].source.is_in_doaj | False |
| locations[0].source.display_name | Proceedings of the AAAI Conference on Artificial Intelligence |
| locations[0].source.host_organization | https://openalex.org/P4310320058 |
| locations[0].source.host_organization_name | Association for the Advancement of Artificial Intelligence |
| locations[0].source.host_organization_lineage | https://openalex.org/P4310320058 |
| locations[0].source.host_organization_lineage_names | Association for the Advancement of Artificial Intelligence |
| locations[0].license | |
| locations[0].pdf_url | https://ojs.aaai.org/index.php/AAAI/article/download/33646/35801 |
| locations[0].version | publishedVersion |
| locations[0].raw_type | journal-article |
| locations[0].license_id | |
| locations[0].is_accepted | True |
| locations[0].is_published | True |
| locations[0].raw_source_name | Proceedings of the AAAI Conference on Artificial Intelligence |
| locations[0].landing_page_url | https://doi.org/10.1609/aaai.v39i14.33646 |
| indexed_in | crossref |
| authorships[0].author.id | https://openalex.org/A5016128874 |
| authorships[0].author.orcid | https://orcid.org/0000-0002-6035-2425 |
| authorships[0].author.display_name | Ronghua Jin |
| authorships[0].author_position | first |
| authorships[0].raw_author_name | Ruiqi Jin |
| authorships[0].is_corresponding | False |
| authorships[1].author.id | https://openalex.org/A5100737217 |
| authorships[1].author.orcid | https://orcid.org/0000-0002-0139-5900 |
| authorships[1].author.display_name | Yongmei Liu |
| authorships[1].author_position | middle |
| authorships[1].raw_author_name | Yongmei Liu |
| authorships[1].is_corresponding | False |
| authorships[2].author.id | https://openalex.org/A5057867466 |
| authorships[2].author.orcid | https://orcid.org/0000-0001-7924-8655 |
| authorships[2].author.display_name | Liping Xiong |
| authorships[2].author_position | last |
| authorships[2].raw_author_name | Liping Xiong |
| authorships[2].is_corresponding | False |
| has_content.pdf | True |
| has_content.grobid_xml | True |
| is_paratext | False |
| open_access.is_oa | True |
| open_access.oa_url | https://ojs.aaai.org/index.php/AAAI/article/download/33646/35801 |
| open_access.oa_status | diamond |
| open_access.any_repository_has_fulltext | False |
| created_date | 2025-10-10T00:00:00 |
| display_name | A Modal Logic for Joint Abilities of Structured Strategies with Bounded Complexity |
| has_fulltext | False |
| is_retracted | False |
| updated_date | 2025-11-06T03:46:38.306776 |
| primary_topic.id | https://openalex.org/T11010 |
| primary_topic.field.id | https://openalex.org/fields/17 |
| primary_topic.field.display_name | Computer Science |
| primary_topic.score | 0.9472000002861023 |
| primary_topic.domain.id | https://openalex.org/domains/3 |
| primary_topic.domain.display_name | Physical Sciences |
| primary_topic.subfield.id | https://openalex.org/subfields/1702 |
| primary_topic.subfield.display_name | Artificial Intelligence |
| primary_topic.display_name | Logic, Reasoning, and Knowledge |
| related_works | https://openalex.org/W3013085049, https://openalex.org/W1560496689, https://openalex.org/W1992739770, https://openalex.org/W4386900933, https://openalex.org/W4229058035, https://openalex.org/W3125672081, https://openalex.org/W2028144918, https://openalex.org/W3016746667, https://openalex.org/W1587059467, https://openalex.org/W2962420748 |
| cited_by_count | 0 |
| locations_count | 1 |
| best_oa_location.id | doi:10.1609/aaai.v39i14.33646 |
| best_oa_location.is_oa | True |
| best_oa_location.source.id | https://openalex.org/S4210191458 |
| best_oa_location.source.issn | 2159-5399, 2374-3468 |
| best_oa_location.source.type | conference |
| best_oa_location.source.is_oa | True |
| best_oa_location.source.issn_l | 2159-5399 |
| best_oa_location.source.is_core | False |
| best_oa_location.source.is_in_doaj | False |
| best_oa_location.source.display_name | Proceedings of the AAAI Conference on Artificial Intelligence |
| best_oa_location.source.host_organization | https://openalex.org/P4310320058 |
| best_oa_location.source.host_organization_name | Association for the Advancement of Artificial Intelligence |
| best_oa_location.source.host_organization_lineage | https://openalex.org/P4310320058 |
| best_oa_location.source.host_organization_lineage_names | Association for the Advancement of Artificial Intelligence |
| best_oa_location.license | |
| best_oa_location.pdf_url | https://ojs.aaai.org/index.php/AAAI/article/download/33646/35801 |
| best_oa_location.version | publishedVersion |
| best_oa_location.raw_type | journal-article |
| best_oa_location.license_id | |
| best_oa_location.is_accepted | True |
| best_oa_location.is_published | True |
| best_oa_location.raw_source_name | Proceedings of the AAAI Conference on Artificial Intelligence |
| best_oa_location.landing_page_url | https://doi.org/10.1609/aaai.v39i14.33646 |
| primary_location.id | doi:10.1609/aaai.v39i14.33646 |
| primary_location.is_oa | True |
| primary_location.source.id | https://openalex.org/S4210191458 |
| primary_location.source.issn | 2159-5399, 2374-3468 |
| primary_location.source.type | conference |
| primary_location.source.is_oa | True |
| primary_location.source.issn_l | 2159-5399 |
| primary_location.source.is_core | False |
| primary_location.source.is_in_doaj | False |
| primary_location.source.display_name | Proceedings of the AAAI Conference on Artificial Intelligence |
| primary_location.source.host_organization | https://openalex.org/P4310320058 |
| primary_location.source.host_organization_name | Association for the Advancement of Artificial Intelligence |
| primary_location.source.host_organization_lineage | https://openalex.org/P4310320058 |
| primary_location.source.host_organization_lineage_names | Association for the Advancement of Artificial Intelligence |
| primary_location.license | |
| primary_location.pdf_url | https://ojs.aaai.org/index.php/AAAI/article/download/33646/35801 |
| primary_location.version | publishedVersion |
| primary_location.raw_type | journal-article |
| primary_location.license_id | |
| primary_location.is_accepted | True |
| primary_location.is_published | True |
| primary_location.raw_source_name | Proceedings of the AAAI Conference on Artificial Intelligence |
| primary_location.landing_page_url | https://doi.org/10.1609/aaai.v39i14.33646 |
| publication_date | 2025-04-11 |
| publication_year | 2025 |
| referenced_works_count | 0 |
| abstract_inverted_index.a | 33, 41, 83, 89, 107 |
| abstract_inverted_index.In | 101 |
| abstract_inverted_index.On | 68 |
| abstract_inverted_index.We | 131, 146, 153 |
| abstract_inverted_index.as | 88 |
| abstract_inverted_index.be | 160 |
| abstract_inverted_index.by | 19 |
| abstract_inverted_index.et | 21 |
| abstract_inverted_index.in | 7, 50, 54, 116, 162, 183, 190 |
| abstract_inverted_index.is | 86 |
| abstract_inverted_index.it | 95 |
| abstract_inverted_index.of | 35, 56, 91, 109, 118, 151, 179, 199 |
| abstract_inverted_index.on | 76 |
| abstract_inverted_index.or | 64 |
| abstract_inverted_index.to | 66, 202 |
| abstract_inverted_index.we | 104, 195 |
| abstract_inverted_index.ATL | 24 |
| abstract_inverted_index.LDL | 123 |
| abstract_inverted_index.Liu | 20 |
| abstract_inverted_index.The | 14 |
| abstract_inverted_index.al. | 22 |
| abstract_inverted_index.and | 1, 9, 39, 141, 149, 174, 187, 206 |
| abstract_inverted_index.are | 4, 52, 60, 114, 137 |
| abstract_inverted_index.can | 37, 159 |
| abstract_inverted_index.for | 210 |
| abstract_inverted_index.has | 73 |
| abstract_inverted_index.it. | 211 |
| abstract_inverted_index.the | 69, 166, 171, 176, 184, 191, 197 |
| abstract_inverted_index.two | 208 |
| abstract_inverted_index.use | 132 |
| abstract_inverted_index.ATL, | 47 |
| abstract_inverted_index.been | 74 |
| abstract_inverted_index.case | 186 |
| abstract_inverted_index.done | 161 |
| abstract_inverted_index.from | 62 |
| abstract_inverted_index.give | 207 |
| abstract_inverted_index.goal | 42 |
| abstract_inverted_index.like | 46 |
| abstract_inverted_index.more | 96, 138 |
| abstract_inverted_index.show | 154 |
| abstract_inverted_index.than | 98, 143 |
| abstract_inverted_index.that | 155 |
| abstract_inverted_index.they | 136 |
| abstract_inverted_index.this | 102 |
| abstract_inverted_index.time | 163 |
| abstract_inverted_index.with | 25, 122, 128, 165, 170, 175 |
| abstract_inverted_index.JAADL | 17, 51, 110 |
| abstract_inverted_index.about | 11, 31, 78 |
| abstract_inverted_index.bound | 178 |
| abstract_inverted_index.case. | 193 |
| abstract_inverted_index.hand, | 71 |
| abstract_inverted_index.joint | 2, 26, 204 |
| abstract_inverted_index.logic | 16 |
| abstract_inverted_index.modal | 15 |
| abstract_inverted_index.model | 156, 167 |
| abstract_inverted_index.norms | 201 |
| abstract_inverted_index.ones. | 145 |
| abstract_inverted_index.other | 70 |
| abstract_inverted_index.since | 135 |
| abstract_inverted_index.size, | 168, 173 |
| abstract_inverted_index.terms | 55, 117 |
| abstract_inverted_index.there | 72 |
| abstract_inverted_index.where | 82, 111 |
| abstract_inverted_index.which | 28, 59 |
| abstract_inverted_index.work, | 103 |
| abstract_inverted_index.SJAADL | 158 |
| abstract_inverted_index.agents | 36 |
| abstract_inverted_index.double | 188 |
| abstract_inverted_index.logic) | 126 |
| abstract_inverted_index.making | 94 |
| abstract_inverted_index.pairs, | 93 |
| abstract_inverted_index.states | 65 |
| abstract_inverted_index.syntax | 148 |
| abstract_inverted_index.topics | 6 |
| abstract_inverted_index.(linear | 124 |
| abstract_inverted_index.SJAADL, | 106 |
| abstract_inverted_index.SJAADL. | 152 |
| abstract_inverted_index.ability | 3 |
| abstract_inverted_index.achieve | 40, 203 |
| abstract_inverted_index.bounded | 129 |
| abstract_inverted_index.defined | 53, 115 |
| abstract_inverted_index.dynamic | 125 |
| abstract_inverted_index.enables | 29 |
| abstract_inverted_index.extends | 23 |
| abstract_inverted_index.formula | 172 |
| abstract_inverted_index.natural | 79, 84, 140 |
| abstract_inverted_index.present | 147 |
| abstract_inverted_index.problem | 198 |
| abstract_inverted_index.propose | 105 |
| abstract_inverted_index.whether | 32 |
| abstract_inverted_index.without | 43 |
| abstract_inverted_index.Finally, | 194 |
| abstract_inverted_index.However, | 45 |
| abstract_inverted_index.actions. | 67 |
| abstract_inverted_index.checking | 157 |
| abstract_inverted_index.proposed | 18 |
| abstract_inverted_index.research | 75 |
| abstract_inverted_index.sequence | 90 |
| abstract_inverted_index.strategy | 85 |
| abstract_inverted_index.succinct | 142 |
| abstract_inverted_index.systems. | 13 |
| abstract_inverted_index.abilities | 49, 113 |
| abstract_inverted_index.coalition | 34 |
| abstract_inverted_index.formulas, | 127 |
| abstract_inverted_index.functions | 61 |
| abstract_inverted_index.histories | 63 |
| abstract_inverted_index.important | 5 |
| abstract_inverted_index.introduce | 196 |
| abstract_inverted_index.memoryful | 192 |
| abstract_inverted_index.reasoning | 10, 30, 77 |
| abstract_inverted_index.semantics | 150 |
| abstract_inverted_index.strategic | 48, 80, 112 |
| abstract_inverted_index.strategy. | 100 |
| abstract_inverted_index.variation | 108 |
| abstract_inverted_index.abilities, | 27, 81, 205 |
| abstract_inverted_index.algorithms | 209 |
| abstract_inverted_index.complexity | 177 |
| abstract_inverted_index.coordinate | 38 |
| abstract_inverted_index.formalized | 87 |
| abstract_inverted_index.memoryless | 185 |
| abstract_inverted_index.strategies | 120, 134 |
| abstract_inverted_index.structured | 119, 180 |
| abstract_inverted_index.complexity. | 130 |
| abstract_inverted_index.exponential | 169, 182, 189 |
| abstract_inverted_index.expressive, | 139 |
| abstract_inverted_index.multi-agent | 12 |
| abstract_inverted_index.represented | 121 |
| abstract_inverted_index.strategies, | 58, 181 |
| abstract_inverted_index.Coordination | 0 |
| abstract_inverted_index.determinstic | 144 |
| abstract_inverted_index.synthesizing | 200 |
| abstract_inverted_index.combinatorial | 57, 99 |
| abstract_inverted_index.communication. | 44 |
| abstract_inverted_index.human-friendly | 97 |
| abstract_inverted_index.representation | 8 |
| abstract_inverted_index.condition-action | 92 |
| abstract_inverted_index.nondeterministic | 133 |
| abstract_inverted_index.quasi-polynomial | 164 |
| cited_by_percentile_year | |
| countries_distinct_count | 0 |
| institutions_distinct_count | 3 |
| citation_normalized_percentile.value | 0.33065327 |
| citation_normalized_percentile.is_in_top_1_percent | False |
| citation_normalized_percentile.is_in_top_10_percent | False |