Generation of text from logical formulae

The paper addresses the problem of generating sentences from logical formulae. It describes a simple and efficient algorithm for generating text which has been developed for use in machine translation, but will have wider application in natural language processing. An important property of the algorithm is that the logical form used to generate a sentence need not be one which could have been produced by parsing the sentence: formal equivalence between logical forms is allowed for. This is necessary for a machine translation system, such as the one envisaged in this paper, which uses single declarative grammars of individual languages, and declarative statements of translation equivalences for transfer. In such a system, it cannot be guaranteed that transfer will produce a logical form in the same order as would have been produced by parsing some target-language sentence, and it is not practicable to define a normal form for the logical forms. The algorithm is demonstrated using a categorial grammar and a simple indexed logic, as this allows a particularly clear and elegant formulation. It is shown that the algorithm can be adapted to phrase-structure grammars, and to more complex semantic representations than that used here.     

LOGICAL EMBEDDED PUSH-DOWN AUTOMATA IN TREE-ADJOINING GRAMMAR PARSING

This paper extends the "parsing as deduction" approach to tree-adjoining grammars by showing how a TAG recognition problem can be reduced to a Datalog deduction problem, and presents an SLD selection rule that makes the proof search correspond to a top-down parse using the original grammar. Just as in the DCG extension of context-free grammars, this approach permits nodes to be labeled with firsl-order terms (rather than only atomic symbols). Finally the paper discusses implementation matters, and describes how the control rule can be efficiently implemented in Prolog.     

The Equivalence of Tree Adjoining Grammars and Monadic Linear Context-free Tree Grammars

The equivalence of leaf languages of tree adjoining grammars and monadic linear context-free grammars was shown about a decade ago. This paper presents a proof of the strong equivalence of these grammar formalisms. Non-strict tree adjoining grammars and monadic linear context-free grammars define the same class of tree languages. We also present a logical characterisation of this tree language class showing that a tree language is a member of this class iff it is the two-dimensional yield of an MSO-definable three-dimensional tree language.     

二值命题逻辑中逻辑理论的计量化及应用

在二值命题逻辑系统中,利用势为2的均匀概率测度空间的无穷乘积,通过计算理论[Γ]的全体模型占整个赋值空间的测度定义了理论[Γ]的真度,进而利用理论的真度简化了理论的发散度和相容度的计算公式,给出了由推理的前提集的真度估计其逻辑结论真度的表达式。     

基于量子逻辑的自动机和文法理论

初步建立了基于量子逻辑的自动机和文法理论的基本框架.引入了量子文法(称为l值文法),特别是证明了任意l值正规文法生成的语言(称为量子语言)等价于某种基于量子逻辑且含动作(的自动机(称为l值自动机)识别的语言,反之,任意l值自动机识别的语言等价于某l值正规文法生成的语言.建立了l值泵引理,并得到量子语言的判定性刻画.最后简要讨论了正规文法与量子文法(即l值正规文法)的关系.因此,为进一步研究更复杂的量子自动机(如量子下推自动机和Turing机)和量子文法(如量子上下文无关文法和上下文有关文法)奠定了基础.     

A Fuzzy Inference Network Model for Search Strategy Using Neural Logic Network

In this paper, a fuzzy inference network model for search strategy using neural logic network is presented. The model describes search strategy, and neural logic network is used to search. Fuzzy logic can bring about appropriate inference results by ignoring some information in the reasoning process. Neural logic networks are powerful tools for the reasoning process but not appropriate for the logical reasoning. To model human knowledge, besides the reasoning process capability, the logical reasoning capability is equally important. Another new neural network called neural logic network is able to do the logical reasoning. Because the fuzzy inference is a fuzzy logical reasoning, we construct a fuzzy inference network model based on the neural logic network, extending the existing rule inference network. And the traditional propagation rule is modified.     

Unprovability of the logical characterization of bisimulation

We quickly review labelled Markov processes (LMP) and provide a counterexample showing that in general measurable spaces, event bisimilarity and state bisimilarity differ in LMP. This shows that the Hennessy-Milner logic proposed by Desharnais does not characterize state bisimulation in non-analytic measurable spaces. Furthermore we show that, under current foundations of Mathematics, such logical characterization is unprovable for spaces that are projections of a coanalytic set. Underlying this construction there is a proof that stationary Markov processes over general measurable spaces do not have semi-pullbacks.     

Resolution theorem proving in reified modal logics

This paper is concerned with the application of the resolution theorem proving method to reified logics. The logical systems treated include the branching temporal logics and logics of belief based on K and its extensions. Two important problems concerning the application of the resolution rule to reified systems are identified. The first is the redundancy in the representation of truth functional relationships and the second is the axiomatic reasoning about modal structure. Both cause an unnecessary expansion in the search space. We present solutions to both problems which allow the axioms defining the reified logic to be eliminated from the database during theorem proving hence reducing the search space while retaining completeness. We describe three theorem proving methods which embody our solutions and support our analysis with empirical results.Much of the research reported in this paper was supported by DTI IED SERC grant No. GR/F 35968, and was carried out whilst Han Reichgelt was at the University of Nottingham.     

Learning context-free grammars using tabular representations

We present a novel algorithm using new hypothesis representations for learning context-free grammars from a finite set of positive and negative examples. We propose an efficient hypothesis representation method which consists of a table-like data structure similar to the parse table used in efficient parsing algorithms for context-free grammars such as Cocke-Younger-Kasami algorithm. By employing this representation method, the problem of learning context-free grammars from examples can be reduced to the problem of partitioning the set of nonterminals. We use genetic algorithms for solving this partitioning problem. Further, we incorporate partially structured examples to improve the efficiency of our learning algorithm, where a structured example is represented by a string with some parentheses inserted to indicate the shape of the derivation tree of the unknown grammar. We demonstrate some experimental results using these algorithms and theoretically analyse the completeness of the search space using the tabular method for context-free grammars.     

Implementation of an interpreter for abstract equations

This paper summarizes a project whose goal is the implementation of a useful interpreter for abstract equations that is absolutely faithful to the logical semantics of equations. The interpreter was first distributed to Berkeley UNIX VAX sites in May 1983. The main novelties of the interpreter are strict adherence to semantics based on logical consequences, ‘lazy’ (outermost) evaluation applied uniformly, an implementation based on table-driven pattern matching, with no run-time penalty for large sets of equations, and strict separation of syntactic and semantic processing, so that different syntaxes may be used for different problems.     

A Fuzzy Adaptive Differential Evolution Algorithm

The differential evolution algorithm is a floating-point encoded evolutionary algorithm for global optimization over continuous spaces. The algorithm has so far used empirically chosen values for its search parameters that are kept fixed through an optimization process. The objective of this paper is to introduce a new version of the Differential Evolution algorithm with adaptive control parameters – the fuzzy adaptive differential evolution algorithm, which uses fuzzy logic controllers to adapt the search parameters for the mutation operation and crossover operation. The control inputs incorporate the relative objective function values and individuals of the successive generations. The emphasis of this paper is analysis of the dynamics and behavior of the algorithm. Experimental results, provided by the proposed algorithm for a set of standard test functions, outperformed those of the standard differential evolution algorithm for optimization problems with higher dimensionality.     

一种特殊的上下文无关文法及其语法分析

SAQ系统是一个进行软件规约获取、检验和复用的实验系统，其中以上下文无关文法表示的概念是规约的一部分.SAQ要求将概念的词法和句法定义结合在一个上下文无关文法中.如果用常规的上下文无关文法描述诸如程序设计语言和自然语言等一些复杂概念的语法，则需要把诸如空格和回车等没有实质意义的分隔符包含到语法中去(这种描述方法称为朴素表示法),使得语法描述很累赘.为此，作者设计了一种特殊的上下文无关文法,它把通常上下文无关文法定义中的非终极符集合和终极符集合进行细化.用这种文法可以相对简洁地描述程序语言和自然语言等复杂概     

一个安全协议度量方法及其应用

简要说明了对安全协议进行协议度量和冗余度量的一个基于模态逻辑方法,形式化地给出了协议对安全目标满足度的度量方法定义,并讨论了相应的协议冗余分析和化简方法。给出了对安全协议的内容进行逻辑比较的准则,结合实例分析了两个协议之间的逻辑包含关系。讨论结合逆向推理的两个应用：对基于模态逻辑的协议分析中隐含假设的分析方法,协议设计和生成方法。     

The construction of a fuzzy inference network by extension of the rule inference network

Fuzzy logic can bring about inappropriate inferences as a result of ignoring some information in the reasoning process. Neural networks are powerful tools for pattern processing, but are not appropriate for the logical reasoning needed to model human knowledge. The use of a neural logic network derived from a modified neural network, however, makes logical reasoning possible. In this paper, we construct a fuzzy inference network by extending the rule–inference network based on an existing neural logic network. The propagation rule used in the existing rule–inference network is modified and applied. In order to determine the belief value of a proposition pertaining to the execution part of the fuzzy rules in a fuzzy inference network, the nodes connected to the proposition to be inferenced should be searched for. The search costs are compared and evaluated through application of sequential and priority searches for all the connected nodes.     

Graph grammars for evolutionary 3D design

A new interactive evolutionary 3D design system is presented. The representation is based on graph grammars, a fascinating and powerful formalism in which nodes and edges are iteratively rewritten by rules analogous to those of context-free grammars and shape grammars. The nodes of the resulting derived graph are labelled with Euclidean coordinates: therefore the graph fully represents a 3D beam design. Results from user-guided runs are presented, demonstrating the flexibility of the representation. Comparison with results using an alternative graph representation demonstrates that the graph grammar search space is more rich in organised designs. A set of numerical features are defined over designs. They are shown to be effective in distinguishing between the designs produced by the two representations, and between designs labelled by users as good or bad. The features allow the definition of a non-interactive fitness function in terms of proximity to target feature vectors. In non-interactive experiments with this fitness function, the graph grammar representation out-performs the alternative graph representation, and evolution out-performs random search.     

Standard versus uniform binary search and their variants in learned static indexing: The case of the searching on sorted data benchmarking software platform

Learned Indexes use a model to restrict the search of a sorted table to a smaller interval. Typically, a final binary search is done using the lower_bound routine of the Standard C++ library. Recent studies have shown that on current processors other search approaches (such as k-ary search) can be more efficient in some applications. Using the SOSD learned indexing benchmarking software, we extend these results to show that k-ary search is indeed a better choice when using learned indexes. We highlight how such a choice may be dependent on the computer architecture used, for example, Intel I7 or Apple M1, and provide guidelines for the selection of the Search routine within the learned indexing framework.     

量子自动机的刻画

澄清了各类量子自动机之间的相互关系,并给出了量子自动机的各种等价刻画定理.引入G-量子自动机、g-量子自动机、(广义)量子自动机及G-量子文法和g-量子文法,并阐明了它们与其他量子自动机之间的等价关系.在一定条件下讨论了G(g)-量子自动机与G(g)-量子文法的等价性,从而解决了关于量子文法产生量子正规语言的问题.讨论了量子语言与正规语言的关系,特别是回答了Gudder提出的两个公开问题.最后,给出了一种减少状态空间维数的方法.     

On Some Transformations of Features in Machine Learning in Medicine

A new view is given to supervised classification problems by precedents on the basis of logical approaches and the possibility of their application in medicine. The basic logical and logical statistical models of classification (basic definitions, search, processing, and application of logical regularities of classes (LRCs); transition to other feature spaces; and the method of optimal reliable decompositions) and their verification are presented. Numerous applications in medicine and two problems of qualification assessment and choice of the treatment method are considered.