### Book

## 28th International Symposium on Algorithms and Computation, ISAAC 2017

Let G = (V,E) be an undirected graph, T ⊆ V be a set of terminals. Then a natural combinatorial problem consists in finding the maximum number of vertex-disjoint paths connecting distinct terminals. For this problem, a clever construction suggested by Gallai reduces it to computing a maximum non-bipartite matching and thus gives an O ( m √n log n 2 /m log n ) -Time algorithm (hereinafter n := |V |, m := |E|). Now let us consider the fractional relaxation, i.e. allow T-path packings with arbitrary nonnegative real weights. It is known that there always exists a half-integral solution, that is, one only needs to assign weights 0, 1/2 , 1 to maximize the total weight of T-paths. It is also known that an optimum half-integral packing can be found in strongly-polynomial time but the actual time bounds are far from being satisfactory. In this paper we present a novel algorithm that solves the half-integral problem within O ( m √n log n 2 /m log n )time, thus matching the complexities of integral and half-integral versions.

This book comprises high-quality, refereed research papers presented at the 2019 International Symposium on Computer Science, Digital Economy and Intelligent Systems (CSDEIS2019): The symposium, held in Moscow, Russia, on 4–6 October 2019, was organized jointly by Moscow State Technical University and the International Research Association of Modern Education and Computer Science. The book discusses the state of the art in areas such as computer science and its technological applications; intelligent systems and intellectual approaches; and digital economics and methodological approaches. It is an excellent reference resource for researchers, undergraduate and graduate students, engineers, and management practitioners interested in computer science and its applications in engineering and management.

This book constitutes the post-conference proceedings of the 8th International Conference on Analysis of Images, Social Networks and Texts, AIST 2019, held in Kazan, Russia, in July 2019.

The 27 full and 8 short papers were carefully reviewed and selected from 134 submissions (of which 21 papers were automatically rejected without being reviewed). The papers are organized in topical sections on general topics of data analysis; natural language processing; social network analysis; analysis of images and video; optimization problems on graphs and network structures; and analysis of dynamic behavior through event data.

**SN Computer Science** is a broad-based, peer reviewed journal that publishes original research in all the disciplines of computer science including various inter-disciplinary aspects. The journal aims to be a global forum of, for, and by the community and offers:

**Rapid peer review**under the expert guidance of a global Editorial Board

**No color or page charges**, free submission, and is

**free to access**for the first two years of publication

**High visibility**Opportunities to Societies/Conferences/Institutes/Laboratories/Corporates to

**‘partner’ with the Journal**and enjoy the benefit of planning and publishing issues in hot areas of research, without being under the pressure of publishing a full-fledge journal

Heaps are well-studied fundamental data structures, having myriads of applications, both theoretical and practical. We consider the problem of designing a heap with an “optimal” extract-min operation. Assuming an arbitrary linear ordering of keys, a heap with n elements typically takes O(log n) time to extract the min-imum. Extracting all elements faster is impossible as this would violate the Ω(n log n) bound for comparison-based sorting. It is known, however, that is takes only O(n + k log k) time to sort just k smallest elements out of n given, which prompts that there might be a faster heap, whose extract-min performance depends on the number of elements extracted so far. In this paper we show that is indeed the case. We present a version of heap that performs insert in O(1) time and takes only O(log ∗ n + log k) time to carry out the k-th extraction (where log ∗ denotes the iterated logarithm). All the above bounds are worst-case.

Abstract

Relativisation involves dependencies which, although unbounded, are constrained with respect to certain island domains. The Lambek calculus **L** can provide a very rudimentary account of relativisation limited to unbounded peripheral extraction; the Lambek calculus with bracket modalities **Lb** can further condition this account according to island domains. However in naïve parsing/theorem-proving by backward chaining sequent proof search for **Lb** the bracketed island domains, which can be indefinitely nested, have to be specified in the linguistic input. In realistic parsing word order is given but such hierarchical bracketing structure cannot be assumed to be given. In this paper we show how parsing can be realised which induces the bracketing structure in backward chaining sequent proof search with **Lb**.

The number of space objects will grow several times in a few years due to the planned launches of constellations of thousands microsatellites. It leads to a significant increase in the threat of satellite collisions. Spacecraft must undertake collision avoidance maneuvers to mitigate the risk. According to publicly available information, conjunction events are now manually handled by operators on the Earth. The manual maneuver planning requires qualified personnel and will be impractical for constellations of thousands satellites. In this paper we propose a new modular autonomous collision avoidance system called "Space Navigator". It is based on a novel maneuver optimization approach that combines domain knowledge with Reinforcement Learning methods.

We assess and compare computer science skills among final-year computer science undergraduates (seniors) in four major economic and political powers that produce approximately half of the science, technology, engineering, and mathematics graduates in the world. We find that seniors in the United States substantially outperform seniors in China, India, and Russia by 0.76–0.88 SDs and score comparably with seniors in elite institutions in these countries. Seniors in elite institutions in the United States further outperform seniors in elite institutions in China, India, and Russia by ∼0.85 SDs. The skills advantage of the United States is not because it has a large proportion of high-scoring international students. Finally, males score consistently but only moderately higher (0.16–0.41 SDs) than females within all four countries.

We investigate the complexity consequences of adding pointer arithmetic to separation logic. Specifically, we study an extension of the points-to fragment of symbolic-heap separation logic with sets of simple “difference constraints” of the form *x*≤*y*+*k*

, where *x* and *y* are pointer variables and *k* is an integer offset. This extension can be considered a practically minimal language for separation logic with pointer arithmetic.

Most significantly, we find that, even for this minimal language, polynomial-time decidability is already impossible: satisfiability becomes NP

-complete, while quantifier-free entailment becomes coNP-complete and quantified entailment becomes *Π**P*2-complete (where *Π**P*2

is the second class in the polynomial-time hierarchy).

However, the language does satisfy the small model property, meaning that any satisfiable formula has a model, and any invalid entailment has a countermodel, of polynomial size, whereas this property fails when richer forms of arithmetical constraints are permitted.

The article examines the problems of defining the term computer simulations of scientific experiments. The first part analyzes the original method for classifying variations of terms proposed by Duran as the most successful for demonstrating significant existing contradictions among philosophers regarding the place and role of computer simulations in the philosophy of science. In the second part of the article, the term itself is formulated by the author through the identification of the main features of computer simulations as a result of studying the nature of experimental data as transferring traces of an experiment from a graphematical space to a representative one. Following the concept of transposition, the author derives a relevant term from the essence of computer simulations revealed by him, claiming a new epistemological significance for such kind of scientific experiments for the philosophy of science.