The Markov School in the 21st Century
The Markov School is the school of mathematics (mostly mathematical logic) arisen in St.Petersburg in the 20th century. Historically, the Markov School has been largely connected with the Steklov Mathematical Institute in St. Petersburg. Today, many Markov School mathematicians have taken up positions in different countries; of course, we do not attempt to restrict this survey only to those who have stayed in St. Petersburg. However, all mathematicians whose work we describe studied in St. Petersburg and, at least for several years and often for decades, worked at the Steklov Mathematical Institute. In this paper, we primarily discuss what has happened over the last two decades, so a certain bias to computational complexity is to be expected.
“Let's be Logical” is a double invitation. Although logic often refers to a disposition of mind that we all share, this disposition might be confused once its theoretical sources are questioned. The present volume offers thirteen articles that address various aspects of the discipline of logic and its methods, notably formalism, the theory of opposition, mathematical truth, and history of logic. This volume has been prepared with the pedagogical concern of making it accessible to a wide audience of logic and philosophy readers.
During his scientific life Albert Visser has contributed to a great variety of disciplines in logic, ranging from provability logics, interpretability, and formal arithmetic to philosophy, linguistics and formal language semantics. This Liber Amicorum is in honour of his long and distinguished career, and nicely bears tribe to the diversity of Albert Visser's interests. Filed with contributions from his colleagues, the book illustrates the important role thatAlbert Visser plays and has played as a logician in the Netherlands and abroad.
Virtual network services that span multiple data centers are important to support emerging data-intensive applications in fields such as bioinformatics and retail analytics. Successful virtual network service composition and maintenance requires flexible and scalable “constrained shortest path management” both in the management plane for virtual network embedding (VNE) or network function virtualization service chaining (NFV-SC), as well as in the data plane for traffic engineering (TE). In this paper, we show analytically and empirically that leveraging constrained shortest paths within recent VNE, NFV-SC and TE algorithms can lead to network utilization gains (of up to 50%) and higher energy efficiency. The management of complex VNE, NFV-SC and TE algorithms can be, however, intractable for large scale substrate networks due to the NP-hardness of the constrained shortest path problem. To address such scalability challenges, we propose a novel, exact constrained shortest path algorithm viz., neighborhoods method (NM). Our NM uses novel search space reduction techniques and has a theoretical quadratic speed-up making it practically faster (by an order of magnitude) than recent branch-and-bound exhaustive search solutions. Finally, we detail our NM-based SDN controller implementation in a real-world testbed to further validate practical NM benefits for virtual network services.
This article deals with the problem of translations. It covers the history of translation in linguistics and analyzes peculiarities and role of translation in logic. Moreover, the article contains typical examples of embedding operations in terms of dierent logical theories.
We show that the statistical approach to quantum mechanics allows to define a factor related to numeration theory in mathematical logic, and to apply this factor to the study of the nucleus of helium-5 and other light nuclei. In particular, the use of the hidden factor of numbering gives us, instead of the quantum picture of the Bohr orbits for small energies, a purely classical behavior of particles corresponding to the rotation of wave packets around the nucleus.
We investigate the satisfiability problem for Horn fragments of the Halpern-Shoham interval temporal logic depending on the type (box or diamond) of the interval modal operators, the type of the underlying linear order (discrete or dense), and the type of semantics for the interval relations (reflexive or irreflexive). For example, we show that satisfiability of Horn formulas with diamonds is undecidable for any type of linear orders and semantics. On the contrary, satisfiability of Horn formulas with boxes is tractable over both discrete and dense orders under the reflexive semantics and over dense orders under the irreflexive semantics but becomes undecidable over discrete orders under the irreflexive semantics. Satisfiability of binary Horn formulas with both boxes and diamonds is always undecidable under the irreflexive semantics.
Big History emerged as part of this non-linear way of understanding the world. What the co-authors of this paper discovered in working together is that the insights of Complexity Theory, which studies the dynamics of non-linear systems, integrate powerfully with Big History. On one hand, it offers an approach to the dynamics, grounded in work in physics, chemistry, and biology, that Big History studies. On the other, it offers an avenue to a more comprehensive view of the challenges and possible solutions of a non-linear world.