1,866 research outputs found
Monadic Second Order Finite Satisfiability and Unbounded Tree-Width
Full text linkThe finite satisfiability problem of monadic second order logic is decidable only on classes of structures of bounded tree-width by the classic result of Seese. We prove that the following problem is decidable:
Input: (i) A monadic second order logic sentence alpha, and (ii) a sentence beta in the two-variable fragment of first order logic extended with counting quantifiers. The vocabularies of alpha and beta may intersect.
Output: Is there a finite structure which satisfies alpha and beta such that the restriction of the structure to the vocabulary of alpha has bounded tree-width? (The tree-width of the desired structure is not bounded.)
As a consequence, we prove the decidability of the satisfiability problem by a finite structure of bounded tree-width of a logic MS^{exists card} extending monadic second order logic with linear cardinality constraints of the form |X_{1}|+...+|X_{r}| < |Y_{1}|+...+|Y_{s}| on the variables X_i, Y_j of the outer-most quantifier block. We prove the decidability of a similar extension of WS1S
Jeunesse: Lecture suivie
No full textI am delighted to have found this little paperback in a favorite bookshop in Paris. I look forward to using it myself. It brings two of his best illustrators to a pupil's book of Florian's fables. The colored illustrations are not the only help for those of us trying to understand a sometimes difficult author. There are vocabulary notes, comments, and -- especially -- a short discussion of each fable's moral. These discussions are pleasantly candid, as in this comment on "La taupe et les lapins": "La fable de Florian est peut-être moins claire qu'elle n'y paraȋt" (55). Great work on rendering the colored illustrations!Language note: FrenchFloria
Verification of asynchronous mobile-robots in partially-known environments (Best Paper Award)
No full textThis paper establishes a framework based on logic and automata theory in which to model and automatically verify that multiple mobile robots, with sensing abilities, moving asynchronously, correctly perform their tasks. The motivation is from practical scenarios in which the environment is not completely know to the robots, e.g., physical robots exploring a maze, or software agents exploring a hostile network. The framework shows how to express tasks in a logical language, and exhibits an algorithm solving the parameterised verification problem, where the graphs are treated as the parameter. The main assumption that yields decidability is that the robots take a bounded number of turns. We prove that dropping this assumption results in undecidability, even for robots with very limited (“local”) sensing abilities
Fables de Florian, Nouvelle Edition
No full textHere is a small edition, 3¼" x 5¼," of 162 pages. It seems to be identical to Bodemann #274, published by the same people two years earlier. As Bodemann notes in a very short description, the illustrations come as three panels per page. One panel often represents two fables. My favorites among these very small illustrations are "The Blind and the Lame" (18); "Two Bachelors" (48); "Owl and Pigeon" (83); and "Ass and Flute" (111). Do not miss the gigantic crocodile on 120! Illustrations occur facing these pages: 1, 12, 18, 29, 38, 48, 66, 83, 111, and 120. There is an AI at the back.This is a hardbound book (hard cover)Language note: FrenchNo Autho
Resource Bound Analysis (Dagstuhl Seminar 17291)
No full textThis report documents the program and the outcomes of Dagstuhl Seminar 17291 "Resource Bound Analysis". Resource-bound analysis is studied in formal methods and programming languages at different levels of abstraction. The goal of the Dagstuhl seminar was to bring together leading researchers with different backgrounds in resource-bound analysis to address challenging open problems and to facilitate communication across research areas
On the Automated Verification of Web Applications with Embedded SQL
Full text linkA large number of web applications is based on a relational database together with a program, typically a script, that enables the user to interact with the database through embedded SQL queries and commands. In this paper, we introduce a method for formal automated verification of such systems which connects database theory to mainstream program analysis. We identify a fragment of SQL which captures the behavior of the queries in our case studies, is algorithmically decidable, and facilitates the construction of weakest preconditions. Thus, we can integrate the analysis of SQL queries into a program analysis tool chain. To this end, we implement a new decision procedure for the SQL fragment that we introduce. We demonstrate practical applicability of our results with three case studies, a web administrator, a simple firewall, and a conference management system
Low-Level Bi-Abduction (Artifact)
Full text linkBroom is a new static analyzer for C written in OCaml. Broom primarily aims at open programs, i.e., fragments of programs, with dynamic pointer-linked data structures - in particular, various kinds of lists - that employ advanced low-level pointer operations. It is based on separation logic and the principle of bi-abductive reasoning. The artifact is a VirtualBox image of a Linux machine with Ubuntu 20.04 operating system. It contains source code and binary of the Broom tool, benchmarks, and scripts for running our and the competing tools we compare to
Interview with Florian Bieber
No full textInterview with Florian Bieber, lecturer in East European Politics at the University of Kent in Canterbury, England. Interview conducted in Ithaca, NY on March 13, 2009. Dr. Bieber has worked in Belgrade (Serbia) and Sarajevo (Bosnia-Herzegovina) for the European Centre for Minority Issues and has taught at the Central European University, at the University of Sarajevo and at the University of Bologna. He is also the author of a book about Serbian nationalism, entitled Nationalism in Serbia from the Death of Tito to the Fall of Milosevic (Muenster: Lit Verlag, 2005, in German), and another book, Post-War Bosnia: Ethnic Structure, Inequality and Governance of the Public Sector (London: Palgrave, 2006). He?s at Cornell this spring semester of 2009 as the Luigi Einaudi Chair in European and International Studies.Bieber's current book project (01:30)
Bieber's reflections on the 20th anniversary of 1989 (02:00)
On Bieber's background in political science and history (03:19)
When interdisciplinarity works best (5:22)
On the "ghettoization" of the Balkans and its causes/possible solutions (6:30)
Unique contribution of our field to other fields (9:38)
Addressing the ongoing perception of a division of Europe into "East" and "West" (12:04)
On Bieber's interest in the study of nationalism (16:17)
Is there such a thing as "good nationalism"? (19:12)
On Bieber's "European" upbringing and early education (21:34)
Bieber on experiences/opportunities all Europeans should ideally have (24:56)
On the future of Southeastern Europe (26:17)1_ruh0kx6
- …
