Telegram Group & Telegram Channel
Forwarded from Covalue
Нашел качественную диссертацию с обзором состояния дел в model checking на 2010й год:

Weißenbacher, [2010] "Program Analysis with Interpolants"

Вкратце идею проверки моделей можно описать так: мы хотим автоматически верифицировать программы, для этого мы аппроксимируем их моделями, то есть автоматами или системами переходов с конечным набором состояний, задаём спецификацию (обычно в какой-то разновидности пропозициональной темпоральной логики) и с помощью поисковых алгоритмов и эвристик исчерпывающе перебираем состояния модели, проверяя что для них всех спецификация верна.

Концептуально этот подход описывается теорией моделей (одним из двух основных разделов логики, второй - это теория доказательств, на которой основана теория типов и proof assistants). Интересно, что в моделчекинге примерно раз в декаду сменяется доминирующая парадигма, в целом его таймлайн выглядит примерно так:

* 1980е - зарождение самой идеи MC из работ Эдмунда Кларка по вычислению неподвижных точек для систем доказательств в предикат-трансформерах, использование BDD для компактификации состояний
* 1990е - дальнейшее ужатие состояний через partial order reduction, появление предикат-абстракции и CEGAR - методов автоматического конструирования моделей из набора assertions о программе
* 2000е - SAT/SMT-революция и уход от BDD, быстрая аппроксимация через интерполяцию Крейга
* 2010е - Аарон Брэдли изобретает семейство алгоритмов PDR (property directed reachability), где процесс построение инварианта чередуется и взаимодействут с построением контрпримера, взаимно усекая пространства поиска
* 2020е - ажиотаж вокруг техник из машинного обучения

Первые три декады и основные их идеи расписаны в первых двух с половиной главах диссертации (вторая половина третьей и четвертая главы более технические).

#automatedreasoning



group-telegram.com/metaprogramming/404
Create:
Last Update:

Нашел качественную диссертацию с обзором состояния дел в model checking на 2010й год:

Weißenbacher, [2010] "Program Analysis with Interpolants"

Вкратце идею проверки моделей можно описать так: мы хотим автоматически верифицировать программы, для этого мы аппроксимируем их моделями, то есть автоматами или системами переходов с конечным набором состояний, задаём спецификацию (обычно в какой-то разновидности пропозициональной темпоральной логики) и с помощью поисковых алгоритмов и эвристик исчерпывающе перебираем состояния модели, проверяя что для них всех спецификация верна.

Концептуально этот подход описывается теорией моделей (одним из двух основных разделов логики, второй - это теория доказательств, на которой основана теория типов и proof assistants). Интересно, что в моделчекинге примерно раз в декаду сменяется доминирующая парадигма, в целом его таймлайн выглядит примерно так:

* 1980е - зарождение самой идеи MC из работ Эдмунда Кларка по вычислению неподвижных точек для систем доказательств в предикат-трансформерах, использование BDD для компактификации состояний
* 1990е - дальнейшее ужатие состояний через partial order reduction, появление предикат-абстракции и CEGAR - методов автоматического конструирования моделей из набора assertions о программе
* 2000е - SAT/SMT-революция и уход от BDD, быстрая аппроксимация через интерполяцию Крейга
* 2010е - Аарон Брэдли изобретает семейство алгоритмов PDR (property directed reachability), где процесс построение инварианта чередуется и взаимодействут с построением контрпримера, взаимно усекая пространства поиска
* 2020е - ажиотаж вокруг техник из машинного обучения

Первые три декады и основные их идеи расписаны в первых двух с половиной главах диссертации (вторая половина третьей и четвертая главы более технические).

#automatedreasoning

BY Metaprogramming


Warning: Undefined variable $i in /var/www/group-telegram/post.php on line 260

Share with your friend now:
group-telegram.com/metaprogramming/404

View MORE
Open in Telegram


Telegram | DID YOU KNOW?

Date: |

In February 2014, the Ukrainian people ousted pro-Russian president Viktor Yanukovych, prompting Russia to invade and annex the Crimean peninsula. By the start of April, Pavel Durov had given his notice, with TechCrunch saying at the time that the CEO had resisted pressure to suppress pages criticizing the Russian government. So, uh, whenever I hear about Telegram, it’s always in relation to something bad. What gives? The company maintains that it cannot act against individual or group chats, which are “private amongst their participants,” but it will respond to requests in relation to sticker sets, channels and bots which are publicly available. During the invasion of Ukraine, Pavel Durov has wrestled with this issue a lot more prominently than he has before. Channels like Donbass Insider and Bellum Acta, as reported by Foreign Policy, started pumping out pro-Russian propaganda as the invasion began. So much so that the Ukrainian National Security and Defense Council issued a statement labeling which accounts are Russian-backed. Ukrainian officials, in potential violation of the Geneva Convention, have shared imagery of dead and captured Russian soldiers on the platform. The perpetrators use various names to carry out the investment scams. They may also impersonate or clone licensed capital market intermediaries by using the names, logos, credentials, websites and other details of the legitimate entities to promote the illegal schemes. The regulator said it has been undertaking several campaigns to educate the investors to be vigilant while taking investment decisions based on stock tips.
from no


Telegram Metaprogramming
FROM American