Single Step Tableaux for Modal Logics

Single Step Tableaux (SST) are the basis of a calculus for modal logics that combines different features of sequent and prefixed tableaux into a simple, modular, strongly analytic, and effective calculus for a wide range of modal logics.The paper presents a number of the computational results about SST (confluence, decidability, space complexity, modularity, etc.) and compares SST with other formalisms such as translation methods, modal resolution, and Gentzen-type tableaux. For instance, it discusses the feasibility and infeasibility of deriving decision procedures for SST and translation-based methods by replacing loop checking techniques with simpler termination checks.The complexity of searching for validity and logical consequence with SST and other methods is discussed. Minimal conditions on SST search strategies are proven to yield Pspace (and NPtime for S5 and KD45) decision procedures. The paper also presents the methodology underlying the construction of the correctness and completeness proofs.     

Decidability by Resolution for Propositional Modal Logics

The paper shows that satisfiability in a range of popular propositional modal systems can be decided by ordinary resolution procedures. This follows from a general result that resolution combined with condensing, and possibly some additional form of normalization, is a decision procedure for the satisfiability problem in certain so-called path logics. Path logics arise from normal propositional modal logics by the optimized functional translation method. The decision result provides an alternative method of proving decidability for modal logics, as well as closely related systems of artificial intelligence. This alone is not interesting. A more far-reaching consequence of the result has practical value, namely, many standard first-order theorem provers that are based on resolution are suitable for facilitating modal reasoning.     

Deciding Regular Grammar Logics with Converse Through First-Order Logic

We provide a simple translation of the satisfiability problem for regular grammar logics with converse into GF², which is the intersection of the guarded fragment and the 2-variable fragment of first-order logic. The translation is theoretically interesting because it translates modal logics with certain frame conditions into first-order logic, without explicitly expressing the frame conditions. It is practically relevant because it makes it possible to use a decision procedure for the guarded fragment in order to decide regular grammar logics with converse. The class of regular grammar logics includes numerous logics from various application domains. A consequence of the translation is that the general satisfiability problem for every regular grammar logics with converse is in EXPTIME. This extends a previous result of the first author for grammar logics without converse. Other logics that can be translated into GF² include nominal tense logics and intuitionistic logic. In our view, the results in this paper show that the natural first-order fragment corresponding to regular grammar logics is simply GF² without extra machinery such as fixed-point operators.     

A Subset-Matching Size-Bounded Cache for Testing Satisfiability in Modal Logics

The implementation of efficient decision procedures for modal logics is a major research problem in automated deduction. Caching the result of intermediate consistency checks has experimentally proved to be a very important technique for attaining efficiency. Current state-of-the-art systems implement caching mechanisms based on hash tables. In this paper we present a data type – that we call bit matrix – for caching the (in)consistency of sets of formulas. Bit matrices have three distinguishing features: (i) they can be queried for subsets and supersets, (ii) they can be bounded in size, and (iii) if bounded, they can easily implement different policies to resolve which results have to be kept. We have implemented caching mechanisms based on bit matrices and hash tables in *SAT. In *SAT, the bit matrix cache is bounded, and keeps the latest obtained (in)consistency results. We experiment with the benchmarks proposed for the modal logic K at the TABLEAUX Non Classical Systems Comparison (TANCS) 2000. On the basis of the results, we conclude that *SAT performances are improved by (i) caching the results of intermediate consistency checks, (ii) using bit matrices instead of hash tables, and (iii) storing a small number of results in the bit matrices.     

A Benchmark Method for the Propositional Modal Logics K, KT, S4

A lot of methods have been proposed – and sometimes implemented – for proof search in the propositional modal logics K, KT, and S4. It is difficult to compare the usefulness of these methods in practice, since in most cases no or only a few execution times have been published. We try to improve this unsatisfactory situation by presenting a set of benchmark formulas. Note that we do not just list formulas, but give a method that allows us to compare different provers today and in the future. As a starting point we give the results we obtained when we applied this benchmark method to the Logics Workbench (LWB). We hope that the discussion of postulates concerning ATP benchmark helps to obtain improved benchmark methods for other logics, too.     

A set-theoretic translation method for polymodal logics

The paper presents aset-theoretic translation method for polymodal logics that reduces derivability in a large class of propositional polymodal logics to derivability in a very weak first-order set theory . Unlike most existing translation methods, the one we propose applies to any normal complete finitely axiomatizable polymodal logic, regardless of whether it is first-order complete or an explicit semantics is available. The finite axiomatizability of allows one to implement mechanical proof-search procedures via the deduction theorem. Alternatively, more specialized and efficient techniques can be employed. In the last part of the paper, we briefly discuss the application ofset T-resolution to support automated derivability in (a suitable extension of) .This work has been supported by funds MURST 40 and 60%. The second author was supported by a grant from the Italian Consiglio Nazionale delle Ricerche (CNR). A previous version of this paper has appeared as a research report in the ILLC-series, ML-94-09, University of Amsterdam. A short version is to be presented at STACS '95 in Munich.On leave at ILLC, Universiteit van Amsterdam, Plantage Muidergracht, 24, 1018 TV Amsterdam, The Netherlands.     

甘蔗收割机机架虚拟样机的模态分析与优化设计

对甘蔗收割机的机架虚拟样机进行了模态分析，发现其低阶模态振型对甘蔗收获质量的影响并不大，采用一阶方法对机架整体作静力强度优化，保证了结构综合应力在材料许用屈服应力190MPa范围内使整体质量降低约7％．优化后构件尺寸的改变并未影响样机的运动仿真，该尺寸可作为生产物理样机的可靠参考尺寸，从而缩短了研制周期，提升了产品设计的一次成功率，为今后数字样机的创新设计提供了一种新的思路和应用依据．     

多模态界面技术及其在多媒体检索中的应用

多模态界面技术可以通过多种交互式设备和方法的协作 ,极大地促进人机之间相互理解与信息交流。作为信息处理领域的一个热点 ,基于内容的多媒体检索对多模态界面技术有着内在的需求。首先分析了传统的文字 /图形界面技术、多媒体界面技术和多模态界面技术的不同特性 ,进而着重从媒体表示、特征表示与查询、智能检索等方面 ,深入探讨了多模态界面技术在多媒体检索领域的应用特点     

An algorithm for constructing gr?bner bases from characteristic sets and its application to geometry

In Ritt's method, a prime ideal is given by a characteristic set. A characteristic set of a prime ideal is generally not a set of generators of this ideal. In this paper we present a simple algorithm for constructing Gröbner bases of a prime ideal from its characteristic set. We give a method for finding new theorems in geometry as an application of this algorithm.The first author was supported by NSF Grants Nos. DCR-8503498 and CCR-8702108. The computer facility was supported by the NSF/CER Grant at the University of Texas.