{"doi":"10.2168/lmcs-8(4:9)2012","title":"Petri Net Reachability Graphs: Decidability Status of First Order Properties","abstract":"<jats:p>We investigate the decidability and complexity status of model-checking\nproblems on unlabelled reachability graphs of Petri nets by considering\nfirst-order and modal languages without labels on transitions or atomic\npropositions on markings. We consider several parameters to separate decidable\nproblems from undecidable ones. Not only are we able to provide precise borders\nand a systematic analysis, but we also demonstrate the robustness of our proof\ntechniques.</jats:p>","journal":"Logical Methods in Computer Science","year":2012,"id":28762,"datarank":0.8657205703553729,"base_score":2.70805020110221,"endowment":2.70805020110221,"self_citation_contribution":0.40620753016533157,"citation_network_contribution":0.4595130401900413,"self_endowment_contribution":0.40620753016533157,"citer_contribution":0.4595130401900413,"corpus_percentile":null,"corpus_rank":null,"citation_count":14,"citer_count":13,"citers_with_citation_signal":10,"citers_with_endowment":10,"datacite_reuse_total":0,"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":160254,"name":"Stephane Demri","orcid":null,"position":1,"is_corresponding":false},{"id":160256,"name":"Roland Meyer","orcid":null,"position":2,"is_corresponding":false},{"id":160257,"name":"Christophe Morvan","orcid":null,"position":3,"is_corresponding":false},{"id":160253,"name":"Philippe Darondeau","orcid":null,"position":0,"is_corresponding":false}],"reference_count":0,"raw_metadata":{"has_enrichment":true,"base_score":2.70805020110221,"endowment":2.70805020110221,"datacite_reuse_total":0,"file_count":0,"downloads":0,"views":0,"has_version_chain":false,"is_dataset":false,"is_oa":false,"pmid":"24523987","pmcid":null,"openalex_id":"https://openalex.org/W2014969648","authors":[],"funders":[],"total_grants":0,"fwci":1.7356,"citation_percentile":0.84210708,"influential_citations":1,"citation_trend":[{"year":2013,"count":2},{"year":2014,"count":1},{"year":2015,"count":2},{"year":2016,"count":2},{"year":2018,"count":1},{"year":2020,"count":2},{"year":2021,"count":4}],"oa_status":"gold","license":"cc-by","oa_locations":[{"url":"https://lmcs.episciences.org/872/pdf","host_type":"journal"},{"url":"https://lmcs.episciences.org/872/pdf","host_type":"GOLD"},{"url":"https://lmcs.episciences.org/872/pdf","host_type":"publisher"},{"url":"https://doi.org/10.2168/lmcs-8(4:9)2012","host_type":"journal"},{"url":"http://arxiv.org/abs/1210.2972","host_type":"repository"},{"url":"http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.397.5749","host_type":""},{"url":"http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.398.2214","host_type":""},{"url":"http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.763.8997","host_type":""},{"url":"https://inria.hal.science/hal-00743935","host_type":"repository"},{"url":"https://doaj.org/article/cc6947ddf4cc417e873772caefa431cc","host_type":"repository"},{"url":"https://arxiv.org/pdf/1210.2972","host_type":"repository"}],"fields_of_study":["Petri Nets in System Modeling","Formal Methods in Verification","Model-Driven Software Engineering Techniques","Computer Science","Mathematics"],"mesh_terms":[],"keywords":["Decidability","Reachability","Undecidable problem","Petri net","Reachability problem","Computer science","Robustness (evolution)","Stochastic Petri net","Discrete mathematics","Theoretical computer science","Mathematics","Algorithm"],"sdg_mappings":[],"linked_datasets":[],"clinical_trials":[],"software_tools":[],"database_accessions":[],"source":"live","citation_network_status":"fetched"},"created_at":"2026-06-08T22:06:28.865961Z","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":[]}