The first order definability of graphs: Upper bounds for quantifier depth

Let D(G) denote the minimum quantifier depth of a first order sentence that defines a graph G up to isomorphism in terms of the adjacency and equality relations. Call two vertices of G similar if they have the same adjacency to any other vertex and denote the maximum number of pairwise similar vertices in G by σ(G). We prove that σ(G)+1?D(G)?max{σ(G)+2,(n+5)/2}, where n denotes the number of vertices of G. In particular, D(G)?(n+5)/2 for every G with no transposition in the automorphism group. If G is connected and has maximum degree d, we prove that for a constant . A linear lower bound for graphs of maximum degree 3 with no transposition in the automorphism group follows from an earlier result by Cai, Fürer, and Immerman [An optimal lower bound on the number of variables for graph identification, Combinatorica 12(4) (1992) 389-410]. Our upper bounds for D(G) hold true even if we allow only definitions with at most one alternation in any sequence of nested quantifiers.In passing we establish an upper bound for a related number D(G,G^′), the minimum quantifier depth of a first order sentence which is true on exactly one of graphs G and G^′. If G and G^′ are non-isomorphic and both have n vertices, then D(G,G^′)?(n+3)/2. This bound is tight up to an additive constant of 1. If we additionally require that a sentence distinguishing G and G^′ is existential, we prove only a slightly weaker bound D(G,G^′)?(n+5)/2.     

Mining information from time series in the form of sentences of natural language

The goal of this paper is to provide a more detailed explanation of the principles how special formulas that characterize properties of trend of time series can be formed and how they are interpreted. Then we show how these formulas can be used in a tectogrammatical tree that construes special sentences of natural language, using which information on behavior of time series is provided. We also outline the principles of mining this information. The last part is devoted to application of the theory of intermediate quantifiers to mining summarized information on time series also in sentences of natural language.     

基于混合遗传算法的MPRM最小化

MPRM(Mixed-Polarity Reed-Muller)最小化是RM(Reed-Muller)电路逻辑综合过程中一个非常重要的阶段,对于输入数较多的布尔函数,传统遗传算法(Genetic Algorithm,GA)在解决MPRM最小化问题时收敛过早.提出了一种基于混合遗传算法(Hybrid Genetic Algorithm,HGA)的MPRM最小化算法,该算法将基于相异度的局部改善策略结合到GA算法的迭代过程中.局部改善策略对种群中最佳个体和与之相异度最大的个体实施交叉操作生成新个体,并将新个体与最佳或最差个体进行竞争.将所提算法应用于一组具有较多输入数的MCNC基准电路,并与其他智能MPRM最小化算法进行比较.结果表明,局部改善策略能够避免算法陷入局部极小,增强了全局收敛能力.与模拟退火遗传算法(Simulated Annealing Genetic Algorithm,SAGA)相比,HGA算法在获得类似结果的前提下提高了时间效率;与Hybrid multi-valued DPSO算法相比,HGA在得到基本相同的算法结果时,时间效率亦基本相同.     

On modal logics arising from scattered locally compact Hausdorff spaces

For a topological space X, let $\mathsf{L}(X)$ be the modal logic of X where □ is interpreted as interior (and hence ◇ as closure) in X. It was shown in [3] that the modal logics S4, S4.1, S4.2, S4.1.2, S4.Grz, ${\mathsf{S4}.\mathsf{Grz}}_n$ ($n\ge 1$), and their intersections arise as $\mathsf{L}(X)$ for some Stone space X. We give an example of a scattered Stone space whose logic is not such an intersection. This gives an affirmative answer to [3, Question 6.2]. On the other hand, we show that a scattered Stone space that is in addition hereditarily paracompact does not give rise to a new logic; namely we show that the logic of such a space is either S4.Grz or ${\mathsf{S4}.\mathsf{Grz}}_n$ for some $n\ge 1$. In fact, we prove this result for any scattered locally compact open hereditarily collectionwise normal and open hereditarily strongly zero-dimensional space.     

Highly Sensitive INHIBIT and XOR Logic Gates Based on ICT and ACQ Emission Switching of a Porphyrin Derivative

Fluorescence‐switch‐based logic devices are very sensitive compared with most of the reported devices based on UV/Vis absorption systems. Herein, we demonstrate that a simple molecule, 5,10,15,20‐tetra‐(4‐aminophenyl)porphyrin (TAPP), shows protonation‐induced multiple emission switches through intramolecular charge transfer and/or aggregation‐caused quenching. Highly sensitive INHIBIT and XOR logic gates can be achieved by combining the intermolecular assembly with the intramolecular photoswitching of diprotonated TAPP (TAPPH₂²⁺). In addition, molecular simulations have been performed by DFT for a better understanding of the emission‐switching processes.     

基于荧光素衍生物单分子器件的二进制全减器和全加器

合成了一种随p H值变化具有5种互变分子结构的新型荧光素衍生物QHF+.通过紫外-可见吸收光谱研究了不同p H值下QHF+发生转化产生的5种结构的特征谱图,并以此为基础设计了二进制逻辑电路.在乙醇/水(体积比为1∶1)混合溶剂体系中,采用等摩尔的H+或OH-作为化学输入信号,选取424和490nm波长下的特定吸光度或透射率作为标准阈值,通过比较紫外-可见吸收光谱的变化,平行实现了多个逻辑门(XOR和INH或AND和XOR)的运算,模拟了二进制全减器和全加器的运行.     

THE Σλ-CALCULUS AND DERIVED PROGRAM FORMS

Abstract

The Σλ-calculus is an extension of an applied λ-calculus designed to abstract parallel and non-deterministic function application evaluation. The abstraction is extended to include Landin's closure, and constant terms and a special form of the conditional allows the regular logics to be developed along the lines of the Hilbert-Ackermann approach. The regular logics are used to characterize derived conditionals in extensions to Dijkstra's weakest preconditions. It is shown that various styles of programming—top-down, bottom-up, recursive and iterative—axe expressible in the Σλ-calculus. Lists and streams are found to be useful in expressing time-dependent behaviour of computational systems. An approximate Church-Rosser Theorem is given.     

Cluster analysis of local convergent sequences of structures

The cluster analysis of very large objects is an important problem, which spans several theoretical as well as applied branches of mathematics and computer science. Here we suggest a novel approach: under assumption of local convergence of a sequence of finite structures we derive an asymptotic clustering. This is achieved by a blend of analytic and geometric techniques, and particularly by a new interpretation of the authors' representation theorem for limits of local convergent sequences, which serves as a guidance for the whole process. Our study may be seen as an effort to describe connectivity structure at the limit (without having a defined explicit limit structure) and to pull this connectivity structure back to the finite structures in the sequence in a continuous way. © 2017 Wiley Periodicals, Inc. Random Struct. Alg., 51, 674–728, 2017     

First order limits of sparse graphs: Plane trees and path‐width

Ne?et?il and Ossona de Mendez introduced the notion of first order convergence as an attempt to unify the notions of convergence for sparse and dense graphs. It is known that there exist first order convergent sequences of graphs with no limit modeling (an analytic representation of the limit). On the positive side, every first order convergent sequence of trees or graphs with no long path (graphs with bounded tree‐depth) has a limit modeling. We strengthen these results by showing that every first order convergent sequence of plane trees (trees with embeddings in the plane) and every first order convergent sequence of graphs with bounded path‐width has a limit modeling. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 50, 612–635, 2017