Усовершенствованная формальная логика / Учебник по теории автоматов

Question

Я знаю, что это больше вопрос математики / формального языка / автоматов / компьютерных наук, чем вопроса программирования, но я надеюсь, что смогу получить совет по понятному учебнику (не неразборчивой монографии) по формальная логика вне исчисления высказываний и предикатов. Меня особенно интересует монадическая логика второго порядка и Büchi Automata .

На данный момент я нашел только Теорию автоматов и ее приложения Бахадыра Хусаинова, Анила Нероде. Автоматы, логика и бесконечные игры Автор: Эрих Гредель, Томас Уилке (ред.). И Формальные модели систем связи: языки, автоматы и монадическая логика второго порядка Бенедикт Боллиг .... Путь через голову.

Answer 1

Так что это лучшая учебная программа, с которой я могу пойти:

Для начинающих в логике:

Питер Дж. Кэмерон, Наборы, логика и категории , Springer, Серия Sprinter, бакалавриат по математике, 1999, URL .

Джеймс Л. Хейн, Дискретные структуры, логика и вычислимость , Jones & Bartlett Publishers, 2009 (3-е изд) URL .

Логика для информатика.

Для начинающих в автоматах и ​​на официальных языках:

Майкл Сипсер, Введение в теорию вычислений , Курс технологии, 2005 (2-й), URL .

и

Алан П. Паркс, Введение в языки, машины и логику , Springer, 2002.

и

Питер Линц, Введение в формальные языки и автоматы , Jones & Bartlett Publishers, 2000 (3-е изд.) URL .

и

Джон Э. Хопкрофт и Джеффри Д. Уллман, Введение в теорию автоматов, языки и вычисления , Аддисон Уэсли, 1979, (1-е изд), ISBN: 0-201-02988-X; URL .

Логика среднего уровня (бакалавриат):

D. Эббингхаус, Математическая логика , Springer, URL .

или

Эллиот Мендельсон, Введение в математическую логику , URL

Продвинутый уровень (выпускник):

Вольфганг Томас, Языки, автоматы и логика , 1996.

Леоний Либкин, Элементы теории конечных моделей , Springer, 2004, URL , TOC .

Для исследований

Бенедикт Болли, Формальные модели систем связи , Springer, 2006, URL .

Гредель, Эрих; Томас, Вольфганг; Wilke, Thomas (Eds.), Автоматы, логики и бесконечные игры , Springer, 2002, URL ,

Answer 2

У вас, кажется, есть конкретная тема, которую вы хотите найти в книге, поэтому я посмотрел на индекс некоторых книг в Amazon. Хотя я никогда не читал эту книгу, Теория вычислений Декстера Козена может заинтересовать вас.

Büchi automation, 155, 159, 161, 283, 298, 343
      determinization, 167-170

monadic second-order theory
    of n successors, 154
    of successor, 154-159

Покрытые страницы в Автоматы лекции 25 по бесконечным строкам и S1S , первая страница доступна для предварительного просмотра по ссылке.

Теория вычислений http://ecx.images -amazon.com / images / I / 51JKHJGWBRL._BO2,204,203,35, -76_AA240_SH20_OU01_.jpg

Answer 3

Я слышал хорошие вещи о Майкла Сипсера * Введение в теорию вычислений . У меня есть это прямо передо мной, хотя я еще не начал читать это.

Answer 4

Вы будете немного удивлены, но я думаю, что книга, которую вы ищете, это «Основы баз данных» Абитебула, Халла и Виану (также известные как «Книга Алисы», потому что Алиса нарисована на обложке и звезды в диалогах с авторами во вступлении к главе). Это не книга о SQL, а о теории баз данных - логика и ее реализация в программах и функциях - поэтому в ней много говорится о сложности и вычислимости языков запросов; и авторы прилагают большие усилия, чтобы быть дружелюбными и общительными.

Answer 5

Я помню, как читал о Büchi Automata в Принципы проверки моделей , что кажется довольно хорошей книгой. Конечно, основное внимание уделяется приложению к проверке модели, но проверка модели в большинстве случаев логична.

Answer 6

Возможно, это не совсем то, что вы ищете, но я многому научился из Модальной логики Блэкберна и его коллег , и я узнал то, что я знаю об автоматах, из речи Джурафски и Мартина и обработка языка , особенно Глава 2. Если ничего другого, то оба предоставляют отличную основу для дальнейших исследований.