Topological Logics with Connectedness over Euclidean Spaces
We consider the quantifier-free languages, Bc and Bc°, obtained by augmenting the signature of Boolean algebras with a unary predicate representing, respectively, the property of being connected, and the property of having a connected interior. These languages are interpreted over the regular closed sets of Rn (n ≥ 2) and, additionally, over the regular closed semilinear sets of Rn. The resulting logics are examples of formalisms that have recently been proposed in the Artificial Intelligence literature under the rubric Qualitative Spatial Reasoning. We prove that the satisfiability problem for Bc is undecidable over the regular closed semilinear sets in all dimensions greater than 1, and that the satisfiability problem for Bc and Bc° is undecidable over both the regular closed sets and the regular closed semilinear sets in the Euclidean plane. However, we also prove that the satisfiability problem for Bc° is NP-complete over the regular closed sets in all dimensions greater than 2, while the corresponding problem for the regular closed semilinear sets is ExpTime-complete. Our results show, in particular, that spatial reasoning is much harder over Euclidean spaces than over arbitrary topological spaces.
This book constitutes the proceedings of the 13th International Computer Science Symposium in Russia, CSR 2018, held in Moscow, Russia, in May 2018.
The 24 full papers presented together with 7 invited lectures were carefully reviewed and selected from 42 submissions. The papers cover a wide range of topics such as algorithms and data structures; combinatorial optimization; constraint solving; computational complexity; cryptography; combinatorics in computer science; formal languages and automata; algorithms for concurrent and distributed systems; networks; and proof theory and applications of logic to computer science.
The language RCC8RCC8is a widely-studied formalism for describing topological arrangements of spatial regions. The variables of this language range over the collection of non-empty, regular closed sets of n -dimensional Euclidean space, here denoted RC+(Rn)RC+(Rn), and its non-logical primitives allow us to specify how the interiors, exteriors and boundaries of these sets intersect. The key question is the satisfiability problem : given a finite set of atomic RCC8RCC8-constraints in m variables, determine whether there exists an m -tuple of elements of RC+(Rn)RC+(Rn)satisfying them. These problems are known to coincide for all n≥1n≥1, so that RCC8RCC8-satisfiability is independent of dimension. This common satisfiability problem is NLogSpace-complete. Unfortunately, RCC8RCC8lacks the means to say that a spatial region comprises a ‘single piece’, and the present article investigates what happens when this facility is added. We consider two extensions of RCC8RCC8: RCC8cRCC8c, in which we can state that a region is connected , and RCC8c∘RCC8c∘, in which we can instead state that a region has a connected interior. The satisfiability problems for both these languages are easily seen to depend on the dimension n , for n≤3n≤3. Furthermore, in the case of RCC8c∘RCC8c∘, we show that there exist finite sets of constraints that are satisfiable over RC+(R2)RC+(R2), but only by ‘wild’ regions having no possible physical meaning. This prompts us to consider interpretations over the more restrictive domain of non-empty, regular closed, polyhedral sets, RCP+(Rn)RCP+(Rn). We show that (a) the satisfiability problems for RCC8cRCC8c(equivalently, RCC8c∘RCC8c∘) over RC+(R)RC+(R)and RCP+(R)RCP+(R)are distinct and both NP-complete; (b) the satisfiability problems for RCC8cRCC8cover RC+(R2)RC+(R2)and RCP+(R2)RCP+(R2)are identical and NP-complete; (c) the satisfiability problems for RCC8c∘RCC8c∘over RC+(R2)RC+(R2)and RCP+(R2)RCP+(R2)are distinct, and the latter is NP-complete. Decidability of the satisfiability problem for RCC8c∘RCC8c∘over RC+(R2)RC+(R2)is open. For n≥3n≥3, RCC8cRCC8cand RCC8c∘RCC8c∘are not interestingly different from RCC8RCC8. We finish by answering the following question: given that a set of RCC8cRCC8c- or RCC8c∘RCC8c∘-constraints is satisfiable over RC+(Rn)RC+(Rn)or RCP+(Rn)RCP+(Rn), how complex is the simplest satisfying assignment? In particular, we exhibit, for both languages, a sequence of constraints ΦnΦn, satisfiable over RCP+(R2)RCP+(R2), such that the size of ΦnΦngrows polynomially in n , while the smallest configuration of polygons satisfying ΦnΦn cuts the plane into a number of pieces that grows exponentially. We further show that, over RC+(R2)RC+(R2), RCC8cRCC8c again requires exponentially large satisfying diagrams, while RCC8c∘RCC8c∘ can force regions in satisfying configurations to have infinitely many components.
We prove that the bound from the theorem on 'economic' maps is best possible. Namely, for m > n + d we construct a map from an n-dimensional simplex to an m-dimensional Euclidean space for which (and for any close map) there exists a d-dimensional plane whose preimage has cardinality not less than the upper bound \(dn + n + 1)/(m - n - d)] + d from the theorem on 'economic' maps. Bibliography: 16 titles.
We investigate regular realizability (RR) problems, which are the prob- lems of verifying whether intersection of a regular language – the input of the problem – and fixed language called filter is non-empty. In this pa- per we focus on the case of context-free filters. Algorithmic complexity of the RR problem is a very coarse measure of context-free languages com- plexity. This characteristic is compatible with rational dominance. We present examples of P-complete RR problems as well as examples of RR problems in the class NL. Also we discuss RR problems with context- free filters that might have intermediate complexity. Possible candidates are the languages with polynomially bounded rational indices.
We prove that the bound from the theorem on ‘economic’ maps is best possible. Namely, for m > n + d we construct a map from an n-dimensional simplex to an m-dimensional Euclidean space for which (and for any close map) there exists a d-dimensional plane whose preimage has cardinality not less than the upper bound ⌈(dn + n + 1)/(m − n − d)⌉ + d from the theorem on ‘economic’ maps.
This book constitutes the refereed proceedings of the 23rd Annual Symposium on Combinatorial Pattern Matching, CPM 2012, held in Helsinki, Finalnd, in July 2012. The 33 revised full papers presented together with 2 invited talks were carefully reviewed and selected from 60 submissions. The papers address issues of searching and matching strings and more complicated patterns such as trees, regular expressions, graphs, point sets, and arrays. The goal is to derive non-trivial combinatorial properties of such structures and to exploit these properties in order to either achieve superior performance for the corresponding computational problems or pinpoint conditions under which searches cannot be performed efficiently. The meeting also deals with problems in computational biology, data compression and data mining, coding, information retrieval, natural language processing, and pattern recognition.
We study the following computational problem: for which values of k, the majority of n bits MAJn can be computed with a depth two formula whose each gate computes a majority function of at most k bits? The corresponding computational model is denoted by MAJk o MAJk. We observe that the minimum value of k for which there exists a MAJk o MAJk circuit that has high correlation with the majority of n bits is equal to Θ(n1/2). We then show that for a randomized MAJk o MAJk circuit computing the majority of n input bits with high probability for every input, the minimum value of k is equal to n2/3+o(1). We show a worst case lower bound: if a MAJk o MAJk circuit computes the majority of n bits correctly on all inputs, then k ≥ n13/19+o(1). This lower bound exceeds the optimal value for randomized circuits and thus is unreachable for pure randomized techniques. For depth 3 circuits we show that a circuit with k = O(n2/3) can compute MAJn correctly on all inputs.
This book constitutes the refereed proceedings of the 44th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2018, held in Krems, Austria, in January/February 2018. The 48 papers presented in this volume were carefully reviewed and selected from 97 submissions. They were organized in topical sections named: foundations of computer science; software engineering: advances methods, applications, and tools; data, information and knowledge engineering; network science and parameterized complexity; model-based software engineering; computational models and complexity; software quality assurance and transformation; graph structure and computation; business processes, protocols, and mobile networks; mobile robots and server systems; automata, complexity, completeness; recognition and generation; optimization, probabilistic analysis, and sorting; filters, configurations, and picture encoding; machine learning; text searching algorithms; and data model engineering.
The Lambek calculus can be considered as a version of non-commutative intuitionistic linear logic. One of the interesting features of the Lambek calculus is the so-called “Lambek’s restriction,” that is, the antecedent of any provable sequent should be non-empty. In this paper we discuss ways of extending the Lambek calculus with the linear logic exponential modality while keeping Lambek’s restriction. We present several versions of the Lambek calculus extended with exponential modalities and prove that those extensions are undecidable, even if we take only one of the two divisions provided by the Lambek calculus.
We consider certain spaces of functions on the circle, which naturally appear in harmonic analysis, and superposition operators on these spaces. We study the following question: which functions have the property that each their superposition with a homeomorphism of the circle belongs to a given space? We also study the multidimensional case.
We consider the spaces of functions on the m-dimensional torus, whose Fourier transform is p -summable. We obtain estimates for the norms of the exponential functions deformed by a C1 -smooth phase. The results generalize to the multidimensional case the one-dimensional results obtained by the author earlier in “Quantitative estimates in the Beurling—Helson theorem”, Sbornik: Mathematics, 201:12 (2010), 1811 – 1836.
We consider the spaces of function on the circle whose Fourier transform is p-summable. We obtain estimates for the norms of exponential functions deformed by a C1 -smooth phase.
This proceedings publication is a compilation of selected contributions from the “Third International Conference on the Dynamics of Information Systems” which took place at the University of Florida, Gainesville, February 16–18, 2011. The purpose of this conference was to bring together scientists and engineers from industry, government, and academia in order to exchange new discoveries and results in a broad range of topics relevant to the theory and practice of dynamics of information systems. Dynamics of Information Systems: Mathematical Foundation presents state-of-the art research and is intended for graduate students and researchers interested in some of the most recent discoveries in information theory and dynamical systems. Scientists in other disciplines may also benefit from the applications of new developments to their own area of study.