{"doi":"10.1007/978-3-030-89716-1_4","title":"Recent Advances on Reachability Problems for Valence Systems (Invited Talk)","abstract":"<jats:title>Abstract</jats:title><jats:p>Valence systems are an abstract model of computation that consists of a finite-state control and some storage mechanism. In contrast to traditional models, the storage mechanism is not fixed, but given as a parameter. This allows us to precisely state questions like: For which storage mechanisms is the reachability problem decidable?</jats:p><jats:p>This survey reports on recent results that aim to understand the impact of the storage mechanism on decidability and complexity of several variants of the reachability problem. The considered problems are configuration reachability, model-checking first-order logic with reachability, and reachability under bounded context switching and scope-boundedness.</jats:p>","journal":"Lecture Notes in Computer Science","year":2021,"id":626848,"datarank":0.16479184330021646,"base_score":1.0986122886681096,"endowment":1.0986122886681096,"self_citation_contribution":0.16479184330021646,"citation_network_contribution":0.0,"self_endowment_contribution":0.16479184330021646,"citer_contribution":0.0,"corpus_percentile":null,"corpus_rank":null,"citation_count":2,"citer_count":0,"citers_with_citation_signal":0,"citers_with_endowment":0,"datacite_reuse_total":2,"is_dataset":false,"is_dataset_confidence":null,"is_data_producer":false,"deposit_databanks":null,"is_oa":false,"file_count":0,"downloads":0,"has_version_chain":false,"published_date":null,"fair_score":null,"fair_percentile":null,"algorithm_id":"datarank_citation_only_1hop_v6","ranking_scope":"data_only","authors":[{"id":1621726,"name":"Georg Zetzsche","orcid":"0000-0002-6421-4388","position":0,"is_corresponding":false}],"reference_count":0,"raw_metadata":{"has_enrichment":true,"resolved":true,"title":"Recent Advances on Reachability Problems for Valence Systems (Invited Talk)","abstract":"<jats:title>Abstract</jats:title><jats:p>Valence systems are an abstract model of computation that consists of a finite-state control and some storage mechanism. In contrast to traditional models, the storage mechanism is not fixed, but given as a parameter. This allows us to precisely state questions like: For which storage mechanisms is the reachability problem decidable?</jats:p><jats:p>This survey reports on recent results that aim to understand the impact of the storage mechanism on decidability and complexity of several variants of the reachability problem. The considered problems are configuration reachability, model-checking first-order logic with reachability, and reachability under bounded context switching and scope-boundedness.</jats:p>","is_dataset_classified":null,"base_score":1.0986122886681096,"endowment":1.0986122886681096,"datacite_reuse_total":2,"file_count":0,"downloads":0,"views":0,"has_version_chain":false,"is_dataset":false,"is_oa":false,"pmid":"19767382","pmcid":null,"openalex_id":"https://openalex.org/W3208672221","authors":[],"funders":[],"total_grants":0,"fwci":0.8096,"citation_percentile":0.68808621,"influential_citations":0,"citation_trend":[{"year":2022,"count":1},{"year":2024,"count":1}],"oa_status":"hybrid","license":"cc-by","oa_locations":[{"url":"https://link.springer.com/content/pdf/10.1007%2F978-3-030-89716-1_4.pdf","host_type":"book series"},{"url":"https://link.springer.com/content/pdf/10.1007%2F978-3-030-89716-1_4.pdf","host_type":"publisher"},{"url":"https://link.springer.com/content/pdf/10.1007/978-3-030-89716-1_4","host_type":"publisher"},{"url":"https://doi.org/10.1007/978-3-030-89716-1_4","host_type":"book series"}],"fields_of_study":["Formal Methods in Verification","Logic, programming, and type systems","semigroups and automata theory"],"mesh_terms":[],"keywords":["Reachability","Decidability","Reachability problem","Computer science","Computation","Scope (computer science)","Bounded function","Theoretical computer science","Context (archaeology)","Algorithm","Mathematics","Programming language"],"sdg_mappings":[],"linked_datasets":[{"doi":"10.4230/lipics.icalp.2026.191","title":"Infinite-State Games with Energy Objectives Beyond Counters","publisher":"Schloss Dagstuhl – Leibniz-Zentrum für Informatik","resource_type":"ConferencePaper"},{"doi":"10.4230/lipics.icalp.2026.2","title":"Decidability and Complexity Borders of Reachability Problems (Invited Talk)","publisher":"Schloss Dagstuhl – Leibniz-Zentrum für Informatik","resource_type":"ConferencePaper"}],"clinical_trials":[],"software_tools":[],"database_accessions":[],"source":"live","citation_network_status":"fetched"},"created_at":"2026-08-04T15:25:37.828999Z","pmid":null,"pmcid":null,"fwci":null,"citation_percentile":null,"influential_citations":0,"oa_status":null,"license":null,"views":0,"total_file_size_bytes":0,"version_count":0,"fair_f":null,"fair_a":null,"fair_i":null,"fair_r":null,"fair_zscore":null,"fair_rationale":null,"fair_model":null,"fair_agent_version":null,"fair_fulltext_source":null,"fair_has_llm":null,"fair_computed_at":null,"clinical_trials":[],"software_tools":[],"db_accessions":[],"linked_datasets":[],"topics":[]}