Infinite Convergent String-rewriting Systems and Cross-sections for Finitely Presented Monoids

A finitely presented monoid has a decidable word problem if and only if it can be presented by some left-recursive convergent string-rewriting system if and only if it has a recursive cross-section. However, regular cross-sections or even context-free cross-sections do not suffice. This is shown by presenting examples of finitely presented monoids with decidable word problems that do not admit regular cross-sections, and that, hence, cannot be presented by left-regular convergent string-rewriting systems. Also examples of finitely presented monoids with decidable word problems are presented that do not even admit context-free cross-sections. On the other hand, it is shown that each finitely presented monoid with a decidable word problem has a finite presentation that admits a cross-section which is a Church–Rosser language. Finally we address the notion of left-regular convergent string-rewriting systems that are tractable.     

Distributed synthesis for well-connected architectures

We study the synthesis problem for external linear or branching specifications and distributed, synchronous architectures with arbitrary delays on processes. External means that the specification only relates input and output variables. We introduce the subclass of uniformly well-connected (UWC) architectures for which there exists a routing allowing each output process to get the values of all inputs it is connected to, as soon as possible. We prove that the distributed synthesis problem is decidable on UWC architectures if and only if the output variables are totally ordered by their knowledge of input variables. We also show that if we extend this class by letting the routing depend on the output process, then the previous decidability result fails. Finally, we provide a natural restriction on specifications under which the whole class of UWC architectures is decidable.     

On the decidability of termination of query evaluation in transitive-closure logics for polynomial constraint databases

The formalism of constraint databases, in which possibly infinite data sets are described by Boolean combinations of polynomial inequality and equality constraints, has its main application area in spatial databases. The standard query language for polynomial constraint databases is first-order logic over the reals. Because of the limited expressive power of this logic with respect to queries that are important in spatial data base applications, various extensions have been introduced. We study extensions of first-order logic with different types of transitive-closure operators and we are in particular interested in deciding the termination of the evaluation of queries expressible in these transitive-closure logics. It turns out that termination is undecidable in general. However, we show that the termination of the transitive closure of a continuous function graph in the two-dimensional plane, viewed as a binary relation over the reals, is decidable, and even expressible in first-order logic over the reals. Based on this result, we identify a particular transitive-closure logic for which termination of query evaluation is decidable and which is more expressive than first-order logic over the reals. Furthermore, we can define a guarded fragment in which exactly the terminating queries of this language are expressible.     

Ranking of System Elements Based on Fuzzy Relation of Influence and Transitive Closure

The author proposes a method of elements ranking in multi-functional system using the fuzzy relations theory. The problem is formulated as an automatic classification based on the transitive closure of the fuzzy similarity relation. The original information about the system is given as a fuzzy relation of influence of elements’ failures on the performance of system’s functions. To calculate the degrees of element’s influence on the functions performance, we use the comparison of all influences with the least influence by 9-point Saaty scale. The proposed method relaxes the assumption about the independence and the binary-state (up-down) of elements. The possible fields of application are multi-functional systems with ill-defined structures such as organizational, ergatic, military, etc.     

基于限界传递相似度图的FCA概念相似度计算方法

使用相似度图计算FCA概念相似度需要构造相似关系的传递闭包,对于复杂问题会导致相似度图规模过大,从而影响相似度评价的效率.为了降低相似度图规模,提出一种基于限界传递相似度图的FCA概念相似度计算方法.该方法首先通过限定传递相似关系的长度来避免构造相似关系的传递闭包,得到的限界传递相似度图中忽略了长度超过界限且对区分FCA概念无用的传递相似关系,能够有效压缩相似度图的规模;然后给出了动态传递相似度计算方法和由限界传递相似度图构建二部图的方法.实验结果表明,使用限界传递相似度图能够在不损失计算结果准确度的情况下有效提高FCA概念相似度计算的效率.     

Attribute grammars and recursive program schemes I

We show that an attribute system can be translated (in a certain way) into a recursive program scheme if and only if it is strongly noncircular. This property introduced by Kennedy and Warren [20] is decidable in polynomial time. We obtain an algorithm to decide the equivalence problem for purely synthesized attribute systems.     

On decidability of LTL model checking for process rewrite systems

We establish a decidability boundary of the model checking problem for infinite-state systems defined by Process Rewrite Systems (PRS) or weakly extended Process Rewrite Systems (wPRS), and properties described by basic fragments of action-based Linear Temporal Logic (LTL) with both future and past operators. It is known that the problem for general LTL properties is decidable for Petri nets and for pushdown processes, while it is undecidable for PA processes.We show that the problem is decidable for wPRS if we consider properties defined by LTL formulae with only modalities strict eventually, strict always, and their past counterparts. Moreover, we show that the problem remains undecidable for PA processes even with respect to the LTL fragment with the only modality until or the fragment with modalities next and infinitely often.     

参数计算中核心化技术及其应用

在参数计算与复杂性理论中,一个参数问题是固定参数可解的问题当且仅当该问题是可核心化的.核心化技术是参数化算法设计中应用最为广泛、有效的技术,是参数理论中的一个研究热点.通过实例分析对比了最主要的4种核心化技术的基本思想、应用特点和方法,总结了核心化技术在cover类、packing类和cut类等几个重要领域中的应用成果,展望核心化技术的进一步研究方向并加以分析讨论,针对核心化新技术研究和某些热点问题,提出了可能采取的核心优化方法和思路.     

Decidability Equivalence between the Star Problem and the Finite Power Problem in Trace Monoids

In the last decade, research on the star problem in trace monoids (is the iteration of a recognizable language also recognizable?) has pointed out the importance of the finite power property to achieve partial solutions to this problem. We prove that the star problem is decidable in some trace monoid if and only if, in the same monoid, it is decidable whether a recognizable language has the finite power property. Intermediate results allow us to give a shorter proof for the decidability of the two previous problems in every trace monoid without a C4 submonoid. We also deal with some earlier ideas, conjectures, and questions which have been raised in the research on the star problem and the finite power property, e.g., we show the decidability of these problems for recognizable languages which contain at most one non-connected trace. Received April 29, 1999, and in revised form November 8, 2000 and in final form November 24, 2000. Online publication February 26, 2001.     

Notions of Sameness by Default and their Application to Anaphora, Vagueness, and Uncertain Reasoning

We motivate and formalize the idea of sameness by default: two objects are considered the same if they cannot be proved to be different. This idea turns out to be useful for a number of widely different applications, including natural language processing, reasoning with incomplete information, and even philosophical paradoxes. We consider two formalizations of this notion, both of which are based on Reiter’s Default Logic. The first formalization is a new relation of indistinguishability that is introduced by default. We prove that the corresponding default theory has a unique extension, in which every two objects are indistinguishable if and only if their non-equality cannot be proved from the known facts. We show that the indistinguishability relation has some desirable properties: it is reflexive, symmetric, and, while not transitive, it has a transitive “flavor.” The second formalization is an extension (modification) of the ordinary language equality by a similar default: two objects are equal if and only if their non-equality cannot be proved from the known facts. It appears to be less elegant from a formal point of view. In particular, it gives rise to multiple extensions. However, this extended equality is better suited for most of the applications discussed in this paper.     

Decidable First-Order Theories of One-Step Rewriting in Trace Monoids

We prove that the first-order theory of the one-step rewriting relation associated with a trace rewriting system is decidable but in general not elementary. This extends known results on semi-Thue systems but our proofs use new methods; these new methods yield the decidability of local properties expressed in first-order logic augmented by modulo-counting quantifiers. Using the main decidability result, we define several subclasses of trace rewriting systems for which the confluence problem is decidable.     

On pebble automata for data languages with decidable emptiness problem

In this paper we study a subclass of pebble automata (PA) for data languages for which the emptiness problem is decidable. Namely, we show that the emptiness problem for weak 2-pebble automata is decidable, while the same problem for weak 3-pebble automata is undecidable. We also introduce the so-called top view weak PA. Roughly speaking, top view weak PA are weak PA where the equality test is performed only between the data values seen by the two most recently placed pebbles. The emptiness problem for this model is still decidable. It is also robust: alternating, non-deterministic and deterministic top view weak PA have the same recognition power; and are strong enough to accept all data languages expressible in Linear Temporal Logic with the future-time operators, augmented with one register freeze quantifier.     

A note on the equivalence problem of rational formal power series

It is shown that the equivalence problem for K-Σ-automata is undecidable for a communicative semiring K. This contrasts with the Equality Theorem of Eilenberg which implies that the problem is decidable if K is a field.     

Decidable containment of recursive queries

One of the most important reasoning tasks on queries is checking containment, i.e., verifying whether one query yields necessarily a subset of the result of another one. Query containment is crucial in several contexts, such as query optimization, query reformulation, knowledge-base verification, information integration, integrity checking, and cooperative answering. Containment is undecidable in general for Datalog, the fundamental language for expressing recursive queries. On the other hand, it is known that containment between monadic Datalog queries and between Datalog queries and unions of conjunctive queries are decidable. It is also known that containment between unions of conjunctive two-way regular path queries, which are queries used in the context of semistructured data models containing a limited form of recursion in the form of transitive closure, is decidable. In this paper, we combine the automata-theoretic techniques at the base of these two decidability results to show that containment of Datalog in union of conjunctive two-way regular path queries is decidable in 2EXPTIME. By sharpening a known lower bound result for containment of Datalog in union of conjunctive queries we show also a matching lower bound.     

An equational logic based approach to the security problem against inference attacks on object-oriented databases

A query is said to be secure against inference attacks by a user if there exists no database instance for which the user can infer the result of the query, using only authorized queries to the user. In this paper, first, the security problem against inference attacks on object-oriented databases is formalized. The definition of inference attacks is based on equational logic. Secondly, the security problem is shown to be undecidable, and a decidable sufficient condition for a given query to be secure under a given schema is proposed. The idea of the sufficient condition is to over-estimate inference attacks using over-estimated results of static type inference. The third contribution is to propose subclasses of schemas and queries for which the security problem becomes decidable. Lastly, the decidability of the security problem is shown to be incomparable with the static type inferability, although the tightness of the over-estimation of the inference attacks is affected in a large degree by that of the static type inference.     

On intuitionistic fuzzy topologies based on intuitionistic fuzzy reflexive and transitive relations

Topologies and rough set theory are widely used in the research field of machine learning and cybernetics. An intuitionistic fuzzy rough set, which is the result of approximation of an intuitionistic fuzzy set with respect to an intuitionistic fuzzy approximation space, is an extension of fuzzy rough sets. For further studying the theories and applications of intuitionistic fuzzy rough sets, in this paper, we investigate the topological structures of intuitionistic fuzzy rough sets. We show that an intuitionistic fuzzy rough approximation space can induce an intuitionistic fuzzy topological space in the sense of Lowen if and only if the intuitionistic fuzzy relation in the approximation space is reflexive and transitive. We also examine the sufficient and necessary conditions that an intuitionistic fuzzy topological space can be associated with an intuitionistic fuzzy reflexive and transitive relation such that the induced lower and upper intuitionistic fuzzy rough approximation operators are, respectively, the intuitionistic fuzzy interior and closure operators of the given topology.     

Rewriting systems and word problems in a free partially commutative monoid

We show that, for finite Thue systems that are confluent modulo the equivalence relation induced by partial commutativity, the word problem is decidable in linear time. In addition, we show that there is a polynomial-time algorithm that on input a finite Thue system will determine whether the Thue system is confluent modulo the equivalence relation induced by partial commutativity.     

Two-way counter machines and finite-state transducers†

Consider the emptiness problem for deterministic two-way finite-state automata that are augmented by a bounded-reversal counter and the equivalence problem for deterministic two-way finite-state transducers. The first problem was posed by Ibarra while the second problem restricted to the case that accepting configurations are also halting configurations was posed by Ehrich and Yau. Recently the first problem restricted to devices that accept only bounded languages as well as the restricted version of the second problem have been shown decidable. Here these two problems are shown decidable also in their general form.     

单可表示类的特征

择优模型是目前常识推理领域中最常用的语义结构之一。在择优模型中有一类重要的模型－单射择优模型,近年来,众多的学者对该模型类从各种角度进行了研究,但一个重要而基本的问题,即何种类型的择优后承具有单射择优模型,虽经多位学者的研究到现在仍然悬而未解。目前,最好的结果Freund在有限语言限制下证明了“择优后承具有单射择优模型当且仅当它满足弱析取合理性”。文中提出择优模型的一种转换,将此转换应用于Kraus,Leham及Magidor提出的KLM模型上,在一般语言框架下证明了“满足弱析取合理性的择优后承必具有单射择优模型”,从而将该问题的研究推进了一步。     

Decidable fragments of many-sorted logic

Many natural specifications use types. We investigate the decidability of fragments of many-sorted first-order logic. We identified some decidable fragments and illustrated their usefulness by formalizing specifications considered in the literature. Often the intended interpretations of specifications are finite. We prove that the formulas in these fragments are valid iff they are valid over the finite structures. We extend these results to logics that allow a restricted form of transitive closure.