# Questions tagged [model-checking]

The tag has no usage guidance.

5 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
140 views

### Practical interactive proof schemes for NP-hard problems

Model-checking (in the sense of reachability in a succinct graph) is PSPACE-complete. SAT is NP-complete. Both problems are considered intractable, yet there exist tools capable of solving them on ...
41 views

### Definition of MSO_1 for graph structures

What is the proper definition of MSO$_1$? MSO$_1$ is also called the one-sorted MSO. In contrast, in MSO$_2$, the two-sorted MSO, first order variables and set variables are allowed to be of two ...
103 views

### Approximating liveness properties with safety properties

Given a finite alphabet set $\Sigma$, the set $\Sigma^{\omega}$ of infinite words over $\Sigma$ can be topologized with a metric $d: \Sigma^{\omega} \rightarrow \mathbb{R}$ such as: \$\forall w_1, w_2 ...
{"ft_lang_label":"__label__en","ft_lang_prob":0.8164509,"math_prob":0.93199813,"size":1471,"snap":"2020-24-2020-29","text_gpt3_token_len":363,"char_repetition_ratio":0.10497614,"word_repetition_ratio":0.0,"special_character_ratio":0.23385452,"punctuation_ratio":0.10622711,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9793293,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2020-07-04T06:36:21Z\",\"WARC-Record-ID\":\"<urn:uuid:c1c9cc90-bde9-4410-9dc2-5e44b4b81397>\",\"Content-Length\":\"128922\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:b5c9e970-9cb7-41a5-9f79-f0dd68bd6a9b>\",\"WARC-Concurrent-To\":\"<urn:uuid:4e0f5420-6471-4d19-b238-ed9d3d3ed484>\",\"WARC-IP-Address\":\"151.101.65.69\",\"WARC-Target-URI\":\"https://cstheory.stackexchange.com/questions/tagged/model-checking?tab=Unanswered\",\"WARC-Payload-Digest\":\"sha1:UK2VHSEU6F75VVMK3ISC6BYBI7C7JZP3\",\"WARC-Block-Digest\":\"sha1:SOEYXPLDVY5X5HLONVBLA522ES5EKPPO\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2020/CC-MAIN-2020-29/CC-MAIN-2020-29_segments_1593655884012.26_warc_CC-MAIN-20200704042252-20200704072252-00416.warc.gz\"}"}