Token Games and History-Deterministic Quantitative-Automata Article Swipe
Udi Boker
,
Karoliina Lehtinen
·
YOU?
·
· 2023
· Open Access
·
· DOI: https://doi.org/10.46298/lmcs-19(4:8)2023
YOU?
·
· 2023
· Open Access
·
· DOI: https://doi.org/10.46298/lmcs-19(4:8)2023
A nondeterministic automaton is history-deterministic if its nondeterminism can be resolved by only considering the prefix of the word read so far. Due to their good compositional properties, history-deterministic automata are useful in solving games and synthesis problems. Deciding whether a given nondeterministic automaton is history-deterministic (the HDness problem) is generally a difficult task, which can involve an exponential procedure, or even be undecidable, as is the case for example with pushdown automata. Token games provide a PTime solution to the HDness problem of B\"uchi and coB\"uchi automata, and it is conjectured that 2-token games characterise HDness for all $\omega$-regular automata. We extend token games to the quantitative setting and analyse their potential to help deciding HDness of quantitative automata. In particular, we show that 1-token games characterise HDness for all quantitative (and Boolean) automata on finite words, as well as discounted-sum (DSum), Inf and Reachability automata on infinite words, and that 2-token games characterise HDness of LimInf and LimSup automata, as well as Sup automata on infinite words. Using these characterisations, we provide solutions to the HDness problem of Safety, Reachability, Inf and Sup automata on finite and infinite words in PTime, of DSum automata on finite and infinite words in NP$\cap$co-NP, of LimSup automata in quasipolynomial time, and of LimInf automata in exponential time, where the latter two are only polynomial for automata with a logarithmic number of weights.
Related Topics
Concepts
Nested word
Quantum finite automata
Discrete mathematics
Nondeterministic algorithm
Automata theory
Automaton
ω-automaton
Computer science
P
Mobile automaton
Reachability
Mathematics
Combinatorics
Algorithm
Theoretical computer science
Time complexity
Metadata
- Type
- article
- Language
- en
- Landing Page
- https://doi.org/10.46298/lmcs-19(4:8)2023
- http://lmcs.episciences.org/12506/pdf
- OA Status
- diamond
- Cited By
- 1
- References
- 24
- Related Works
- 10
- OpenAlex ID
- https://openalex.org/W4388293219
All OpenAlex metadata
Raw OpenAlex JSON
- OpenAlex ID
-
https://openalex.org/W4388293219Canonical identifier for this work in OpenAlex
- DOI
-
https://doi.org/10.46298/lmcs-19(4:8)2023Digital Object Identifier
- Title
-
Token Games and History-Deterministic Quantitative-AutomataWork title
- Type
-
articleOpenAlex work type
- Language
-
enPrimary language
- Publication year
-
2023Year of publication
- Publication date
-
2023-11-03Full publication date if available
- Authors
-
Udi Boker, Karoliina LehtinenList of authors in order
- Landing page
-
https://doi.org/10.46298/lmcs-19(4:8)2023Publisher landing page
- PDF URL
-
https://lmcs.episciences.org/12506/pdfDirect link to full text PDF
- Open access
-
YesWhether a free full text is available
- OA status
-
diamondOpen access status per OpenAlex
- OA URL
-
https://lmcs.episciences.org/12506/pdfDirect OA link when available
- Concepts
-
Nested word, Quantum finite automata, Discrete mathematics, Nondeterministic algorithm, Automata theory, Automaton, ω-automaton, Computer science, P, Mobile automaton, Reachability, Mathematics, Combinatorics, Algorithm, Theoretical computer science, Time complexityTop concepts (fields/topics) attached by OpenAlex
- Cited by
-
1Total citation count in OpenAlex
- Citations by year (recent)
-
2025: 1Per-year citation counts (last 5 years)
- References (count)
-
24Number of works referenced by this work
- Related works (count)
-
10Other works algorithmically related by OpenAlex
Full payload
| id | https://openalex.org/W4388293219 |
|---|---|
| doi | https://doi.org/10.46298/lmcs-19(4:8)2023 |
| ids.doi | https://doi.org/10.46298/lmcs-19(4:8)2023 |
| ids.openalex | https://openalex.org/W4388293219 |
| fwci | 0.3089612 |
| type | article |
| title | Token Games and History-Deterministic Quantitative-Automata |
| biblio.issue | |
| biblio.volume | Volume 19, Issue 4 |
| biblio.last_page | |
| biblio.first_page | |
| topics[0].id | https://openalex.org/T10142 |
| topics[0].field.id | https://openalex.org/fields/17 |
| topics[0].field.display_name | Computer Science |
| topics[0].score | 0.9976000189781189 |
| topics[0].domain.id | https://openalex.org/domains/3 |
| topics[0].domain.display_name | Physical Sciences |
| topics[0].subfield.id | https://openalex.org/subfields/1703 |
| topics[0].subfield.display_name | Computational Theory and Mathematics |
| topics[0].display_name | Formal Methods in Verification |
| topics[1].id | https://openalex.org/T10260 |
| topics[1].field.id | https://openalex.org/fields/17 |
| topics[1].field.display_name | Computer Science |
| topics[1].score | 0.9830999970436096 |
| topics[1].domain.id | https://openalex.org/domains/3 |
| topics[1].domain.display_name | Physical Sciences |
| topics[1].subfield.id | https://openalex.org/subfields/1710 |
| topics[1].subfield.display_name | Information Systems |
| topics[1].display_name | Software Engineering Research |
| topics[2].id | https://openalex.org/T10126 |
| topics[2].field.id | https://openalex.org/fields/17 |
| topics[2].field.display_name | Computer Science |
| topics[2].score | 0.982699990272522 |
| topics[2].domain.id | https://openalex.org/domains/3 |
| topics[2].domain.display_name | Physical Sciences |
| topics[2].subfield.id | https://openalex.org/subfields/1702 |
| topics[2].subfield.display_name | Artificial Intelligence |
| topics[2].display_name | Logic, programming, and type systems |
| is_xpac | False |
| apc_list | |
| apc_paid | |
| concepts[0].id | https://openalex.org/C92117001 |
| concepts[0].level | 5 |
| concepts[0].score | 0.607092559337616 |
| concepts[0].wikidata | https://www.wikidata.org/wiki/Q6997829 |
| concepts[0].display_name | Nested word |
| concepts[1].id | https://openalex.org/C174327141 |
| concepts[1].level | 4 |
| concepts[1].score | 0.5965272188186646 |
| concepts[1].wikidata | https://www.wikidata.org/wiki/Q176837 |
| concepts[1].display_name | Quantum finite automata |
| concepts[2].id | https://openalex.org/C118615104 |
| concepts[2].level | 1 |
| concepts[2].score | 0.561408519744873 |
| concepts[2].wikidata | https://www.wikidata.org/wiki/Q121416 |
| concepts[2].display_name | Discrete mathematics |
| concepts[3].id | https://openalex.org/C176181172 |
| concepts[3].level | 2 |
| concepts[3].score | 0.5511906147003174 |
| concepts[3].wikidata | https://www.wikidata.org/wiki/Q3490301 |
| concepts[3].display_name | Nondeterministic algorithm |
| concepts[4].id | https://openalex.org/C116248031 |
| concepts[4].level | 3 |
| concepts[4].score | 0.547603964805603 |
| concepts[4].wikidata | https://www.wikidata.org/wiki/Q214526 |
| concepts[4].display_name | Automata theory |
| concepts[5].id | https://openalex.org/C112505250 |
| concepts[5].level | 2 |
| concepts[5].score | 0.5344198346138 |
| concepts[5].wikidata | https://www.wikidata.org/wiki/Q787116 |
| concepts[5].display_name | Automaton |
| concepts[6].id | https://openalex.org/C92710233 |
| concepts[6].level | 5 |
| concepts[6].score | 0.49648410081863403 |
| concepts[6].wikidata | https://www.wikidata.org/wiki/Q291256 |
| concepts[6].display_name | ω-automaton |
| concepts[7].id | https://openalex.org/C41008148 |
| concepts[7].level | 0 |
| concepts[7].score | 0.47690868377685547 |
| concepts[7].wikidata | https://www.wikidata.org/wiki/Q21198 |
| concepts[7].display_name | Computer science |
| concepts[8].id | https://openalex.org/C134026603 |
| concepts[8].level | 3 |
| concepts[8].score | 0.46722185611724854 |
| concepts[8].wikidata | https://www.wikidata.org/wiki/Q846354 |
| concepts[8].display_name | P |
| concepts[9].id | https://openalex.org/C50348692 |
| concepts[9].level | 4 |
| concepts[9].score | 0.45409271121025085 |
| concepts[9].wikidata | https://www.wikidata.org/wiki/Q6887056 |
| concepts[9].display_name | Mobile automaton |
| concepts[10].id | https://openalex.org/C136643341 |
| concepts[10].level | 2 |
| concepts[10].score | 0.4447995722293854 |
| concepts[10].wikidata | https://www.wikidata.org/wiki/Q1361526 |
| concepts[10].display_name | Reachability |
| concepts[11].id | https://openalex.org/C33923547 |
| concepts[11].level | 0 |
| concepts[11].score | 0.3687772750854492 |
| concepts[11].wikidata | https://www.wikidata.org/wiki/Q395 |
| concepts[11].display_name | Mathematics |
| concepts[12].id | https://openalex.org/C114614502 |
| concepts[12].level | 1 |
| concepts[12].score | 0.36804962158203125 |
| concepts[12].wikidata | https://www.wikidata.org/wiki/Q76592 |
| concepts[12].display_name | Combinatorics |
| concepts[13].id | https://openalex.org/C11413529 |
| concepts[13].level | 1 |
| concepts[13].score | 0.3458919823169708 |
| concepts[13].wikidata | https://www.wikidata.org/wiki/Q8366 |
| concepts[13].display_name | Algorithm |
| concepts[14].id | https://openalex.org/C80444323 |
| concepts[14].level | 1 |
| concepts[14].score | 0.3229145407676697 |
| concepts[14].wikidata | https://www.wikidata.org/wiki/Q2878974 |
| concepts[14].display_name | Theoretical computer science |
| concepts[15].id | https://openalex.org/C311688 |
| concepts[15].level | 2 |
| concepts[15].score | 0.311401903629303 |
| concepts[15].wikidata | https://www.wikidata.org/wiki/Q2393193 |
| concepts[15].display_name | Time complexity |
| keywords[0].id | https://openalex.org/keywords/nested-word |
| keywords[0].score | 0.607092559337616 |
| keywords[0].display_name | Nested word |
| keywords[1].id | https://openalex.org/keywords/quantum-finite-automata |
| keywords[1].score | 0.5965272188186646 |
| keywords[1].display_name | Quantum finite automata |
| keywords[2].id | https://openalex.org/keywords/discrete-mathematics |
| keywords[2].score | 0.561408519744873 |
| keywords[2].display_name | Discrete mathematics |
| keywords[3].id | https://openalex.org/keywords/nondeterministic-algorithm |
| keywords[3].score | 0.5511906147003174 |
| keywords[3].display_name | Nondeterministic algorithm |
| keywords[4].id | https://openalex.org/keywords/automata-theory |
| keywords[4].score | 0.547603964805603 |
| keywords[4].display_name | Automata theory |
| keywords[5].id | https://openalex.org/keywords/automaton |
| keywords[5].score | 0.5344198346138 |
| keywords[5].display_name | Automaton |
| keywords[6].id | https://openalex.org/keywords/ω-automaton |
| keywords[6].score | 0.49648410081863403 |
| keywords[6].display_name | ω-automaton |
| keywords[7].id | https://openalex.org/keywords/computer-science |
| keywords[7].score | 0.47690868377685547 |
| keywords[7].display_name | Computer science |
| keywords[8].id | https://openalex.org/keywords/p |
| keywords[8].score | 0.46722185611724854 |
| keywords[8].display_name | P |
| keywords[9].id | https://openalex.org/keywords/mobile-automaton |
| keywords[9].score | 0.45409271121025085 |
| keywords[9].display_name | Mobile automaton |
| keywords[10].id | https://openalex.org/keywords/reachability |
| keywords[10].score | 0.4447995722293854 |
| keywords[10].display_name | Reachability |
| keywords[11].id | https://openalex.org/keywords/mathematics |
| keywords[11].score | 0.3687772750854492 |
| keywords[11].display_name | Mathematics |
| keywords[12].id | https://openalex.org/keywords/combinatorics |
| keywords[12].score | 0.36804962158203125 |
| keywords[12].display_name | Combinatorics |
| keywords[13].id | https://openalex.org/keywords/algorithm |
| keywords[13].score | 0.3458919823169708 |
| keywords[13].display_name | Algorithm |
| keywords[14].id | https://openalex.org/keywords/theoretical-computer-science |
| keywords[14].score | 0.3229145407676697 |
| keywords[14].display_name | Theoretical computer science |
| keywords[15].id | https://openalex.org/keywords/time-complexity |
| keywords[15].score | 0.311401903629303 |
| keywords[15].display_name | Time complexity |
| language | en |
| locations[0].id | doi:10.46298/lmcs-19(4:8)2023 |
| locations[0].is_oa | True |
| locations[0].source.id | https://openalex.org/S114379355 |
| locations[0].source.issn | 1860-5974 |
| locations[0].source.type | journal |
| locations[0].source.is_oa | True |
| locations[0].source.issn_l | 1860-5974 |
| locations[0].source.is_core | True |
| locations[0].source.is_in_doaj | True |
| locations[0].source.display_name | Logical Methods in Computer Science |
| locations[0].source.host_organization | https://openalex.org/P4310313916 |
| locations[0].source.host_organization_name | Logical Methods in Computer Science e.V. |
| locations[0].source.host_organization_lineage | https://openalex.org/P4310313916 |
| locations[0].source.host_organization_lineage_names | Logical Methods in Computer Science e.V. |
| locations[0].license | cc-by |
| locations[0].pdf_url | http://lmcs.episciences.org/12506/pdf |
| locations[0].version | publishedVersion |
| locations[0].raw_type | journal-article |
| locations[0].license_id | https://openalex.org/licenses/cc-by |
| locations[0].is_accepted | True |
| locations[0].is_published | True |
| locations[0].raw_source_name | Logical Methods in Computer Science |
| locations[0].landing_page_url | https://doi.org/10.46298/lmcs-19(4:8)2023 |
| locations[1].id | pmh:oai:HAL:hal-04271341v1 |
| locations[1].is_oa | True |
| locations[1].source.id | https://openalex.org/S4306402512 |
| locations[1].source.issn | |
| locations[1].source.type | repository |
| locations[1].source.is_oa | False |
| locations[1].source.issn_l | |
| locations[1].source.is_core | False |
| locations[1].source.is_in_doaj | False |
| locations[1].source.display_name | HAL (Le Centre pour la Communication Scientifique Directe) |
| locations[1].source.host_organization | https://openalex.org/I1294671590 |
| locations[1].source.host_organization_name | Centre National de la Recherche Scientifique |
| locations[1].source.host_organization_lineage | https://openalex.org/I1294671590 |
| locations[1].license | cc-by |
| locations[1].pdf_url | |
| locations[1].version | submittedVersion |
| locations[1].raw_type | info:eu-repo/semantics/article |
| locations[1].license_id | https://openalex.org/licenses/cc-by |
| locations[1].is_accepted | False |
| locations[1].is_published | False |
| locations[1].raw_source_name | EISSN: 1860-5974 |
| locations[1].landing_page_url | https://hal.science/hal-04271341 |
| locations[2].id | pmh:oai:doaj.org/article:b50ddae343d74b6ca62594ebc750346c |
| locations[2].is_oa | False |
| locations[2].source.id | https://openalex.org/S4306401280 |
| locations[2].source.issn | |
| locations[2].source.type | repository |
| locations[2].source.is_oa | False |
| locations[2].source.issn_l | |
| locations[2].source.is_core | False |
| locations[2].source.is_in_doaj | False |
| locations[2].source.display_name | DOAJ (DOAJ: Directory of Open Access Journals) |
| locations[2].source.host_organization | |
| locations[2].source.host_organization_name | |
| locations[2].license | |
| locations[2].pdf_url | |
| locations[2].version | submittedVersion |
| locations[2].raw_type | article |
| locations[2].license_id | |
| locations[2].is_accepted | False |
| locations[2].is_published | False |
| locations[2].raw_source_name | Logical Methods in Computer Science, Vol Volume 19, Issue 4 (2023) |
| locations[2].landing_page_url | https://doaj.org/article/b50ddae343d74b6ca62594ebc750346c |
| indexed_in | crossref, doaj |
| authorships[0].author.id | https://openalex.org/A5000415323 |
| authorships[0].author.orcid | https://orcid.org/0000-0003-4322-8892 |
| authorships[0].author.display_name | Udi Boker |
| authorships[0].countries | IL |
| authorships[0].affiliations[0].institution_ids | https://openalex.org/I4210093787 |
| authorships[0].affiliations[0].raw_affiliation_string | RUNI - Reichman University [Herzliya] (8 Ha'Universita st. Herzliya 4610101 - Israel) |
| authorships[0].institutions[0].id | https://openalex.org/I4210093787 |
| authorships[0].institutions[0].ror | https://ror.org/00m6hsp80 |
| authorships[0].institutions[0].type | healthcare |
| authorships[0].institutions[0].lineage | https://openalex.org/I4210093787 |
| authorships[0].institutions[0].country_code | IL |
| authorships[0].institutions[0].display_name | Herzliya Medical Center |
| authorships[0].author_position | first |
| authorships[0].raw_author_name | Udi Boker |
| authorships[0].is_corresponding | False |
| authorships[0].raw_affiliation_strings | RUNI - Reichman University [Herzliya] (8 Ha'Universita st. Herzliya 4610101 - Israel) |
| authorships[1].author.id | https://openalex.org/A5039866284 |
| authorships[1].author.orcid | https://orcid.org/0000-0003-1171-8790 |
| authorships[1].author.display_name | Karoliina Lehtinen |
| authorships[1].countries | FR |
| authorships[1].affiliations[0].institution_ids | https://openalex.org/I21491767, https://openalex.org/I4210114274 |
| authorships[1].affiliations[0].raw_affiliation_string | LIS - Laboratoire d'Informatique et des Systèmes (LIS) (Marseille, Toulon) (Aix Marseille Université – Campus de Saint Jérôme – Bat. Polytech, 52 Av. Escadrille Normandie Niemen, 13397 Marseille Cedex 20 - France) |
| authorships[1].affiliations[1].raw_affiliation_string | MOVE - Modélisation et Vérification (Luminy - France) |
| authorships[1].institutions[0].id | https://openalex.org/I21491767 |
| authorships[1].institutions[0].ror | https://ror.org/035xkbk20 |
| authorships[1].institutions[0].type | education |
| authorships[1].institutions[0].lineage | https://openalex.org/I21491767 |
| authorships[1].institutions[0].country_code | FR |
| authorships[1].institutions[0].display_name | Aix-Marseille Université |
| authorships[1].institutions[1].id | https://openalex.org/I4210114274 |
| authorships[1].institutions[1].ror | https://ror.org/0257sgk90 |
| authorships[1].institutions[1].type | facility |
| authorships[1].institutions[1].lineage | https://openalex.org/I1294671590, https://openalex.org/I143002897, https://openalex.org/I21491767, https://openalex.org/I4210114274 |
| authorships[1].institutions[1].country_code | FR |
| authorships[1].institutions[1].display_name | Laboratoire d’Informatique et Systèmes |
| authorships[1].author_position | last |
| authorships[1].raw_author_name | Karoliina Lehtinen |
| authorships[1].is_corresponding | False |
| authorships[1].raw_affiliation_strings | LIS - Laboratoire d'Informatique et des Systèmes (LIS) (Marseille, Toulon) (Aix Marseille Université – Campus de Saint Jérôme – Bat. Polytech, 52 Av. Escadrille Normandie Niemen, 13397 Marseille Cedex 20 - France), MOVE - Modélisation et Vérification (Luminy - France) |
| has_content.pdf | True |
| has_content.grobid_xml | True |
| is_paratext | False |
| open_access.is_oa | True |
| open_access.oa_url | http://lmcs.episciences.org/12506/pdf |
| open_access.oa_status | diamond |
| open_access.any_repository_has_fulltext | False |
| created_date | 2025-10-10T00:00:00 |
| display_name | Token Games and History-Deterministic Quantitative-Automata |
| has_fulltext | False |
| is_retracted | False |
| updated_date | 2025-11-06T03:46:38.306776 |
| primary_topic.id | https://openalex.org/T10142 |
| primary_topic.field.id | https://openalex.org/fields/17 |
| primary_topic.field.display_name | Computer Science |
| primary_topic.score | 0.9976000189781189 |
| primary_topic.domain.id | https://openalex.org/domains/3 |
| primary_topic.domain.display_name | Physical Sciences |
| primary_topic.subfield.id | https://openalex.org/subfields/1703 |
| primary_topic.subfield.display_name | Computational Theory and Mathematics |
| primary_topic.display_name | Formal Methods in Verification |
| related_works | https://openalex.org/W4386400090, https://openalex.org/W4382203044, https://openalex.org/W2169203237, https://openalex.org/W4310283533, https://openalex.org/W4285173356, https://openalex.org/W1978638999, https://openalex.org/W2368684504, https://openalex.org/W2173305072, https://openalex.org/W2321667159, https://openalex.org/W4388293219 |
| cited_by_count | 1 |
| counts_by_year[0].year | 2025 |
| counts_by_year[0].cited_by_count | 1 |
| locations_count | 3 |
| best_oa_location.id | doi:10.46298/lmcs-19(4:8)2023 |
| best_oa_location.is_oa | True |
| best_oa_location.source.id | https://openalex.org/S114379355 |
| best_oa_location.source.issn | 1860-5974 |
| best_oa_location.source.type | journal |
| best_oa_location.source.is_oa | True |
| best_oa_location.source.issn_l | 1860-5974 |
| best_oa_location.source.is_core | True |
| best_oa_location.source.is_in_doaj | True |
| best_oa_location.source.display_name | Logical Methods in Computer Science |
| best_oa_location.source.host_organization | https://openalex.org/P4310313916 |
| best_oa_location.source.host_organization_name | Logical Methods in Computer Science e.V. |
| best_oa_location.source.host_organization_lineage | https://openalex.org/P4310313916 |
| best_oa_location.source.host_organization_lineage_names | Logical Methods in Computer Science e.V. |
| best_oa_location.license | cc-by |
| best_oa_location.pdf_url | http://lmcs.episciences.org/12506/pdf |
| best_oa_location.version | publishedVersion |
| best_oa_location.raw_type | journal-article |
| best_oa_location.license_id | https://openalex.org/licenses/cc-by |
| best_oa_location.is_accepted | True |
| best_oa_location.is_published | True |
| best_oa_location.raw_source_name | Logical Methods in Computer Science |
| best_oa_location.landing_page_url | https://doi.org/10.46298/lmcs-19(4:8)2023 |
| primary_location.id | doi:10.46298/lmcs-19(4:8)2023 |
| primary_location.is_oa | True |
| primary_location.source.id | https://openalex.org/S114379355 |
| primary_location.source.issn | 1860-5974 |
| primary_location.source.type | journal |
| primary_location.source.is_oa | True |
| primary_location.source.issn_l | 1860-5974 |
| primary_location.source.is_core | True |
| primary_location.source.is_in_doaj | True |
| primary_location.source.display_name | Logical Methods in Computer Science |
| primary_location.source.host_organization | https://openalex.org/P4310313916 |
| primary_location.source.host_organization_name | Logical Methods in Computer Science e.V. |
| primary_location.source.host_organization_lineage | https://openalex.org/P4310313916 |
| primary_location.source.host_organization_lineage_names | Logical Methods in Computer Science e.V. |
| primary_location.license | cc-by |
| primary_location.pdf_url | http://lmcs.episciences.org/12506/pdf |
| primary_location.version | publishedVersion |
| primary_location.raw_type | journal-article |
| primary_location.license_id | https://openalex.org/licenses/cc-by |
| primary_location.is_accepted | True |
| primary_location.is_published | True |
| primary_location.raw_source_name | Logical Methods in Computer Science |
| primary_location.landing_page_url | https://doi.org/10.46298/lmcs-19(4:8)2023 |
| publication_date | 2023-11-03 |
| publication_year | 2023 |
| referenced_works | https://openalex.org/W1535172341, https://openalex.org/W2026128612, https://openalex.org/W1494274610, https://openalex.org/W3209701753, https://openalex.org/W3113412086, https://openalex.org/W2586521831, https://openalex.org/W2405152255, https://openalex.org/W3118078169, https://openalex.org/W2272792315, https://openalex.org/W2907581921, https://openalex.org/W2294334272, https://openalex.org/W2931271882, https://openalex.org/W2070937106, https://openalex.org/W3209808760, https://openalex.org/W1594196576, https://openalex.org/W3006504376, https://openalex.org/W2963656969, https://openalex.org/W2963072428, https://openalex.org/W2953022118, https://openalex.org/W3210996054, https://openalex.org/W4205146527, https://openalex.org/W4403517675, https://openalex.org/W4212847481, https://openalex.org/W2901103347 |
| referenced_works_count | 24 |
| abstract_inverted_index.A | 0 |
| abstract_inverted_index.a | 40, 51, 76, 226 |
| abstract_inverted_index.In | 120 |
| abstract_inverted_index.We | 101 |
| abstract_inverted_index.an | 57 |
| abstract_inverted_index.as | 64, 138, 140, 161, 163 |
| abstract_inverted_index.be | 9, 62 |
| abstract_inverted_index.by | 11 |
| abstract_inverted_index.if | 5 |
| abstract_inverted_index.in | 32, 191, 201, 206, 213 |
| abstract_inverted_index.is | 3, 44, 49, 65, 90 |
| abstract_inverted_index.it | 89 |
| abstract_inverted_index.of | 16, 83, 117, 156, 179, 193, 203, 210, 229 |
| abstract_inverted_index.on | 135, 147, 166, 186, 196 |
| abstract_inverted_index.or | 60 |
| abstract_inverted_index.so | 20 |
| abstract_inverted_index.to | 23, 79, 105, 113, 175 |
| abstract_inverted_index.we | 122, 172 |
| abstract_inverted_index.Due | 22 |
| abstract_inverted_index.Inf | 143, 182 |
| abstract_inverted_index.Sup | 164, 184 |
| abstract_inverted_index.all | 98, 130 |
| abstract_inverted_index.and | 35, 85, 88, 109, 144, 150, 158, 183, 188, 198, 209 |
| abstract_inverted_index.are | 30, 220 |
| abstract_inverted_index.can | 8, 55 |
| abstract_inverted_index.for | 68, 97, 129, 223 |
| abstract_inverted_index.its | 6 |
| abstract_inverted_index.the | 14, 17, 66, 80, 106, 176, 217 |
| abstract_inverted_index.two | 219 |
| abstract_inverted_index.(and | 132 |
| abstract_inverted_index.(the | 46 |
| abstract_inverted_index.DSum | 194 |
| abstract_inverted_index.case | 67 |
| abstract_inverted_index.even | 61 |
| abstract_inverted_index.far. | 21 |
| abstract_inverted_index.good | 25 |
| abstract_inverted_index.help | 114 |
| abstract_inverted_index.only | 12, 221 |
| abstract_inverted_index.read | 19 |
| abstract_inverted_index.show | 123 |
| abstract_inverted_index.that | 92, 124, 151 |
| abstract_inverted_index.well | 139, 162 |
| abstract_inverted_index.with | 70, 225 |
| abstract_inverted_index.word | 18 |
| abstract_inverted_index.PTime | 77 |
| abstract_inverted_index.Token | 73 |
| abstract_inverted_index.Using | 169 |
| abstract_inverted_index.games | 34, 74, 94, 104, 126, 153 |
| abstract_inverted_index.given | 41 |
| abstract_inverted_index.task, | 53 |
| abstract_inverted_index.their | 24, 111 |
| abstract_inverted_index.these | 170 |
| abstract_inverted_index.time, | 208, 215 |
| abstract_inverted_index.token | 103 |
| abstract_inverted_index.where | 216 |
| abstract_inverted_index.which | 54 |
| abstract_inverted_index.words | 190, 200 |
| abstract_inverted_index.HDness | 47, 81, 96, 116, 128, 155, 177 |
| abstract_inverted_index.LimInf | 157, 211 |
| abstract_inverted_index.LimSup | 159, 204 |
| abstract_inverted_index.PTime, | 192 |
| abstract_inverted_index.extend | 102 |
| abstract_inverted_index.finite | 136, 187, 197 |
| abstract_inverted_index.latter | 218 |
| abstract_inverted_index.number | 228 |
| abstract_inverted_index.prefix | 15 |
| abstract_inverted_index.useful | 31 |
| abstract_inverted_index.words, | 137, 149 |
| abstract_inverted_index.words. | 168 |
| abstract_inverted_index.(DSum), | 142 |
| abstract_inverted_index.1-token | 125 |
| abstract_inverted_index.2-token | 93, 152 |
| abstract_inverted_index.B\"uchi | 84 |
| abstract_inverted_index.Safety, | 180 |
| abstract_inverted_index.analyse | 110 |
| abstract_inverted_index.example | 69 |
| abstract_inverted_index.involve | 56 |
| abstract_inverted_index.problem | 82, 178 |
| abstract_inverted_index.provide | 75, 173 |
| abstract_inverted_index.setting | 108 |
| abstract_inverted_index.solving | 33 |
| abstract_inverted_index.whether | 39 |
| abstract_inverted_index.Boolean) | 133 |
| abstract_inverted_index.Deciding | 38 |
| abstract_inverted_index.automata | 29, 134, 146, 165, 185, 195, 205, 212, 224 |
| abstract_inverted_index.deciding | 115 |
| abstract_inverted_index.infinite | 148, 167, 189, 199 |
| abstract_inverted_index.problem) | 48 |
| abstract_inverted_index.pushdown | 71 |
| abstract_inverted_index.resolved | 10 |
| abstract_inverted_index.solution | 78 |
| abstract_inverted_index.weights. | 230 |
| abstract_inverted_index.automata, | 87, 160 |
| abstract_inverted_index.automata. | 72, 100, 119 |
| abstract_inverted_index.automaton | 2, 43 |
| abstract_inverted_index.coB\"uchi | 86 |
| abstract_inverted_index.difficult | 52 |
| abstract_inverted_index.generally | 50 |
| abstract_inverted_index.potential | 112 |
| abstract_inverted_index.problems. | 37 |
| abstract_inverted_index.solutions | 174 |
| abstract_inverted_index.synthesis | 36 |
| abstract_inverted_index.polynomial | 222 |
| abstract_inverted_index.procedure, | 59 |
| abstract_inverted_index.conjectured | 91 |
| abstract_inverted_index.considering | 13 |
| abstract_inverted_index.exponential | 58, 214 |
| abstract_inverted_index.logarithmic | 227 |
| abstract_inverted_index.particular, | 121 |
| abstract_inverted_index.properties, | 27 |
| abstract_inverted_index.Reachability | 145 |
| abstract_inverted_index.characterise | 95, 127, 154 |
| abstract_inverted_index.quantitative | 107, 118, 131 |
| abstract_inverted_index.undecidable, | 63 |
| abstract_inverted_index.Reachability, | 181 |
| abstract_inverted_index.compositional | 26 |
| abstract_inverted_index.NP$\cap$co-NP, | 202 |
| abstract_inverted_index.discounted-sum | 141 |
| abstract_inverted_index.nondeterminism | 7 |
| abstract_inverted_index.quasipolynomial | 207 |
| abstract_inverted_index.$\omega$-regular | 99 |
| abstract_inverted_index.nondeterministic | 1, 42 |
| abstract_inverted_index.characterisations, | 171 |
| abstract_inverted_index.history-deterministic | 4, 28, 45 |
| cited_by_percentile_year.max | 95 |
| cited_by_percentile_year.min | 91 |
| countries_distinct_count | 2 |
| institutions_distinct_count | 2 |
| citation_normalized_percentile.value | 0.60338653 |
| citation_normalized_percentile.is_in_top_1_percent | False |
| citation_normalized_percentile.is_in_top_10_percent | False |