Aplikasi struktur metrik pada poset / kisi di theoryCS

17

Karena istilah ini kelebihan beban, definisi singkat terlebih dahulu. Poset adalah himpunan dianugerahi perintah parsial . Dengan dua elemen , kita dapat mendefinisikan (gabung) sebagai batas atas paling rendah mereka di , dan dengan cara yang sama mendefinisikan (bertemu) (gabung) sebagai batas bawah terbesar. $X$ $\le$ $a,b \in X$ $x \vee y$ $X$ $x \wedge y$

Kisi adalah poset di mana setiap dua elemen memiliki pertemuan unik dan gabungan unik.

Kisi-kisi (dalam bentuk ini) muncul di theoryCS di (secara singkat) teori submodularity (dengan subset lattice) dan clustering (kisi partisi), serta dalam teori domain (yang saya tidak mengerti dengan baik) dan statis analisis.

Tapi saya tertarik pada aplikasi yang menggunakan struktur metrik pada kisi. Contoh sederhana berasal dari pengelompokan, di mana fungsi submodular antimonoton apa pun (antimonoton berarti bahwa jika ) menginduksi metrik $f : X \rightarrow R$ $x \le y, f(x) \le f(y)$

d (x, y) = 2 f (x \land y) - f (x) - f (y)

$d(x,y) = 2f(x \wedge y) - f(x) - f(y)$

Metrik ini telah digunakan secara luas sebagai cara untuk membandingkan dua pengelompokan berbeda dari suatu kumpulan data.

Apakah ada aplikasi kisi lain yang peduli dengan struktur metrik? Saya tertarik pada teori domain / aplikasi analisis statis, tetapi sejauh ini saya belum melihat adanya kebutuhan akan metrik .

reference-request co.combinatorics metrics lattice order-theory Suresh Venkat
sumber

12

Pertama, sebuah komentar. Jenis pertanyaan Anda tergantung pada seberapa geometris maksud Anda kata "metrik". Sangat umum untuk menggunakan ultrametrik dalam semantik dan analisis statis, tetapi ultrametrik cenderung memiliki kombinatorial daripada interpretasi geometris. (Ini adalah varian dari pengamatan bahwa teori domain memiliki aroma topologi kombinatorial daripada penggunaan geometris.)

Yang mengatakan, saya akan memberi Anda contoh bagaimana ini muncul dalam bukti program. Pertama, ingatlah bahwa dalam bukti program, kami ingin menunjukkan bahwa formula yang menggambarkan suatu program berlaku. Secara umum, formula ini tidak harus ditafsirkan dengan boolean, tetapi dapat diambil dari unsur-unsur beberapa kisi nilai kebenaran. Maka formula yang benar adalah hanya satu yang sama dengan bagian atas kisi.

Lebih jauh lagi, ketika menentukan program referensi diri sangat (misalnya, program yang menggunakan kode modifikasi diri sendiri) masalah bisa menjadi sangat sulit. Kami biasanya ingin memberikan spesifikasi program yang rekursif, tetapi mungkin tidak ada struktur induktif yang jelas untuk menggantung definisi. Untuk mengatasi masalah ini, seringkali membantu untuk melengkapi kisi nilai kebenaran dengan struktur metrik tambahan. Kemudian, jika Anda dapat menunjukkan bahwa predikat titik tetap yang Anda inginkan benar-benar kontraktual, Anda dapat mengajukan banding ke teorema titik tetap Banach untuk menyimpulkan bahwa predikat rekursif yang Anda inginkan didefinisikan dengan baik.

Kasing yang paling saya kenal disebut "step-indexing". Dalam pengaturan ini, kami menganggap kisi kami nilai kebenaran menjadi himpunan bagian tertutup , yang elemen-elemennya dapat dengan bebas kita interpretasikan sebagai "panjangnya urutan evaluasi yang dimiliki oleh properti". Bertemu dan bergabung adalah persimpangan dan serikat pekerja, seperti biasa, dan karena kisi telah selesai kita dapat mendefinisikan implikasi Heyting juga. Kisi juga dapat dilengkapi dengan ultrametrik dengan membiarkan jarak antara dua elemen kisi menjadi , di mana adalah elemen terkecil dalam satu set tetapi tidak yang lain. $\Omega$ $\mathbb{N}$ $2^{-n}$ $n$

Kemudian, peta kontraksi Banach yang memberi tahu kita bahwa predikat kontraktual memiliki titik tetap yang unik. Secara intuitif, ini mengatakan bahwa jika kita dapat mendefinisikan predikat yang berlaku untuk langkah-langkah menggunakan versi yang berlaku untuk langkah-langkah , maka kita benar-benar memiliki definisi predikat yang jelas. Jika kita kemudian menunjukkan bahwa predikat sama dengan , maka kita tahu bahwa predikat selalu berlaku untuk program. $p : \Omega \to \Omega$ $n+1$ $n$ $\top = \mathbb{N}$

Neel Krishnaswami
sumber

ah menarik. Dalam menjawab pertanyaan Anda, yang saya pedulikan hanyalah bahwa metriknya hanya itu: itu memenuhi ketimpangan segitiga. Jadi ultrametrik baik-baik saja. Namun, (dan ini adalah kekurangan saya dalam pertanyaan) bagi saya tampaknya penggunaan metrik di sini bersifat struktural, sehingga dapat memperoleh akses ke Banach. Anda tidak peduli dengan metrik itu sendiri (jadi hal-hal seperti mendekati metrik atau menghitungnya tidak relevan). Apakah itu benar ?

Suresh Venkat

4

Ya, kami tidak terlalu peduli dengan metrik. Ini sebenarnya sumber ketidaknyamanan dengan model metrik atau langkah-diindeks - mengapa kita melacak informasi yang tidak kita pedulikan? Menunjukkan bahwa suatu model stabil di bawah kelas perkiraan metrik (mungkin konservatif berkenaan dengan kontraktilitas) sebenarnya akan meningkatkan kenyamanan dengannya.

Neel Krishnaswami

9

Sebagai alternatif dari CPO yang lebih umum digunakan, Arnold dan Nivat menjelajahi ruang metrik sebagai domain semantik denotasional [1]. Dalam tesisnya, Bonsangue [2] mengeksplorasi dualitas antara semantik denotasional dan semantik aksiomatik. Saya menyebutkannya di sini karena memberikan gambaran keseluruhan yang sangat komprehensif.

[1]: A Arnold, M Nivat: Interpretasi Metrik Pohon Tak Terbatas dan Semantik dari Program Rekursif non Deterministik. Teor Comput. Sci. 11: 181-205 (1980).
[2]: MM Dualitas Topologi Bonsangue dalam Semantik volume 8 ENTCS, Elsevier 1998.

Kai
sumber

Fantastis - Saya tidak tahu tesis ini online!

Neel Krishnaswami

3

Saya membiarkan Marcello (Bonsangue) tahu bahwa dia sedang dibicarakan. (Mungkin dia akan bergabung.)

Dave Clarke

5

Ini satu (dari, kebetulan, bagian atas antrian bacaan saya):

Swarat Chaudhuri, Sumit Gulwani dan Roberto Lublinerman. Analisis Kontinuitas Program. POPL 2010.

Para penulis memberikan semantik denotasional untuk bahasa imperatif dengan loop sederhana, menafsirkan ekspresi sebagai fungsi dari nilai-nilai dalam ruang metrik produk yang mendasarinya. Intinya adalah untuk menentukan program mana yang mewakili fungsi kontinu, bahkan di hadapan "jika" dan loop. Mereka bahkan membiarkan pertanyaan tentang kontinuitas terbatas pada input dan output tertentu. (Ini penting untuk menganalisis algoritma Dijkstra, yang kontinu dalam panjang lintasannya, tetapi tidak pada lintasan yang sebenarnya.)

Saya belum melihat apa pun yang membutuhkan ruang metrik - sepertinya itu bisa dilakukan dengan menggunakan topologi umum sejauh ini - tapi saya hanya di halaman 3. :)

Neil Toronto
sumber

1

tentu saja tidak ada poset atau kisi di sini, seperti pada jawaban sebelumnya. itu yang saya lewatkan.

Suresh Venkat

3

Permintaan maaf karena menambahkan jawaban lain, tetapi jawaban ini tidak terkait dengan jawaban saya yang lain di atas.

Ruang metrik yang saya gunakan secara rutin untuk mengganggu (atau mendidik?) Siswa konkurensi adalah jejak tak terbatas. Topologi yang diinduksi adalah tepat yang Alpern dan Schneider [1] digunakan untuk mengkarakterisasi sifat keselamatan dan liveness sebagai batas-tertutup dan padat, masing-masing.

\begin{array}{rcl} d : Σ^{ω} \times Σ^{ω} & ⟶ & R_{\geq 0} \\ (σ, τ) & \mapsto & 2^{- sup {saya \in N | σ |_{saya} = τ |_{saya}}} \end{array}

$\begin{array}{@{}rcl} d : \Sigma^\omega\times\Sigma^\omega & \longrightarrow & \mathbb{R}_{{}\ge 0}\\ % (\sigma,\tau) & \mapsto & 2^{-\sup \{~i\in\mathbb{N} ~|~ \sigma|_i = \tau|_i~\}} \end{array}$

σ |_{i}

$\sigma|_i$

σ

$\sigma$

i

$i$

2^{- \infty} = 0

$2^{-\infty} = 0$

Dalam retrospeksi saya menyadari bahwa jawaban ini juga tidak memiliki bahan penting dari struktur kisi atau poset. Namun struktur kisi seperti itu hadir ketika bergerak satu tingkat ke atas yang oleh Clarkson dan Schneider disebut hyperproperties [2]. Pada saat penulisan ini tidak jelas bagi saya bagaimana cara mengangkat metrik.

[1] B Alpern dan FB Schneider. Menentukan gaya hidup. IPL, 21 (4): 181–185, 1985.
[2] MR Clarkson dan FB Schneider. Hyperproperties. CSF, p51-65, IEEE, 2008.

Kai
sumber

Di sini kita bisa mengetikkan LaTeX sama seperti yang biasa kita lakukan - meletakkan tanda dolar di sekitar \ sum_ {k = 1} ^ nk = \ frac {k (k + 1)} {2} dan kita akan mendapatkan . Lihat posting meta ini untuk informasi lebih lanjut.

\sum_{k = 1}^{n} k = n (n + 1) / 2

$\sum_{k=1}^n k = {n(n+1)}/{2}$

Hsien-Chih Chang 張顯之

@HCH terima kasih, saya telah mengedit posting saya sesuai dan menghapus teriakan terang-terangan untuk saran format.

Kai

Formula yang bagus!

Hsien-Chih Chang 張顯之

Aplikasi struktur metrik pada poset / kisi di theoryCS

Jawaban: