检索结果-内蒙古大学图书馆

Nonerasing, counting, and majority over the linear time hierarchy

INFORMATION AND COMPUTATION 2002年第2期174卷 132-142页

作者： Durand, A More, M Univ Paris 12 Dept Informat LACL F-94010 Creteil France Univ Auvergne Dept Informat IUT LLAIC F-63172 Aubiere France

In this paper, we investigate several extensions of the linear time hierarchy (denoted by LTH). We first prove that it is not necessary to erase the oracle tape between two successive oracle calls, thereby lifting a common restriction on LTH machines. We also define a natural counting extension of LTH and show that it corresponds to a robust notion of counting bounded arithmetic predicates. Finally, we show that the computational power of the majority operator is equivalent to that of the exact counting operator in both contexts. (C) 2002 Elsevier science (USA).

关键词： computational and structural complexity logic in computer science rudimentary relations counting classes

来源：评论

学校读者我要写书评

暂无评论

Extracting models from clause sets saturated under semantic refinements of the resolution rule

引用

INFORMATION AND COMPUTATION 2003年第2期181卷 99-130页

作者： Peltier, N Imag Lab Grenoble CNRS Lab LEIBNIZ F-38031 Grenoble France

We present an algorithm that-given a set of clauses S saturated under some semantic refinements of the resolution calculus-automatically constructs a Herbrand model M of' S. M is represented by a set of atoms with equality and disequality constraints interpreted over the finite tree algebra, hence the problem of evaluating first-order formulae in M is decidable. (C) 2003 Elsevier science (USA). All rights reserved.

关键词： logic in computer science automated deduction automated model building saturation-based methods

来源：评论

学校读者我要写书评

暂无评论

Bisimulation-invariant PTIME and higher-dimensional μ-calculus

引用

THEORETICAL computer science 1999年第1-2期224卷 237-265页

作者： Otto, M Math Grundlagen Informat D-52074 Aachen Germany

Consider the class of all those properties of worlds in finite Kripke structures (or of states in finite transition systems), that are recognizable in polynomial time, and closed under bisimulation equivalence. It is shown that the class of these bisimulation-invariant PTIME queries has a natural logical characterization. It is captured by the straightforward extension of propositional mu-calculus to arbitrary finite dimension. Bisimulation-invariant PTIME, or the modal fragment of PTIME, thus proves to be one of the very rare cases in which a logical characterization is known in a setting of unordered structures. It is also shown that higher-dimensional mu-calculus is undecidable for satisfiability in finite structures, and even Sigma(1)(1)-hard over general structures. (C) 1999 Elsevier science B.V. All rights reserved.

关键词： logic in computer science finite model theory modal logic descriptive complexity process logics model checking

来源：评论

学校读者我要写书评

暂无评论

Abstract deduction and inferential models for type theory

引用

INFORMATION AND COMPUTATION 2010年第7期208卷 737-771页

作者： Gentilini, Paolo Martelli, Maurizio IMATI CNR I-16149 Genoa Italy Univ Genoa DISI I-16146 Genoa Italy

An inferential semantics for full Higher Order logic (HOL) is proposed. The paper presents a constructive notion of model, that being able to capture relevant computational aspects is particularly suited for the applications of HOL to computer science. The inferential semantics is based on the introduction of new abstract deduction structures (ADS) that express the action of the Comprehension Axiom in a Higher Order logic proof. The ADS's allow to define an inferential algebra of higher order potential proof-trees, endowed with two binary operations, the abstraction and the contraction, each consisting of constructive reductions between potential proofs. Typed formulas are interpreted by sequent trees, and the operations between trees correspond to the logical connectives of the interpreted formula. Higher Order logic is sound and complete w.r.t. the given inferential semantics. (C) 2010 Elsevier Inc. All rights reserved.

关键词： logic in computer science Constructive semantics for Higher Order logic Proof-theory

来源：评论

学校读者我要写书评

暂无评论

Model-checking hierarchical structures

引用

JOURNAL OF computer AND SYSTEM scienceS 2012年第2期78卷 461-490页

作者： Lohrey, Markus Univ Stuttgart FMI D-7000 Stuttgart Germany

Hierarchical graph definitions allow a modular description of structures using modules for the specification of repeated substructures. Beside this modularity, hierarchical graph definitions allow us to specify structures of exponential size using polynomial size descriptions. In many cases, this succinctness increases the computational complexity of decision problems when input structures are defined hierarchically. In this paper, the model-checking problem for first-order logic (FO), monadic second-order logic (MSO), and second-order logic (SO) on hierarchically defined input structures is investigated. It is shown that in general these model-checking problems are exponentially harder than their non-hierarchical counterparts, where the input structures are given explicitly. As a consequence, several new complete problems for the levels of the polynomial time hierarchy and the exponential time hierarchy are obtained. Based on classical results of Gaifman and Courcelle, two restrictions on the structure of hierarchical graph definitions that lead to more efficient model-checking algorithms are presented. (C) 2011 Elsevier Inc. All rights reserved.

关键词： Model-checking Hierarchical structures logic in computer science Complexity

来源：评论

学校读者我要写书评

暂无评论

SOME PROBLEMS IN AUTOMATA THEORY WHICH DEPEND ON THE MODELS OF SET THEORY

引用

RAIRO-THEORETICAL INFORMATICS AND APPLICATIONS 2011年第4期45卷 383-397页

作者： Finkel, Olivier CNRS Equipe Log Math Inst Math Jussieu F-75700 Paris France Univ Paris 07 F-75221 Paris 05 France

We prove that some fairly basic questions on automata reading infinite words depend on the models of the axiomatic system ZFC. It is known that there are only three possibilities for the cardinality of the complement of an omega-language L(A) accepted by a Buchi 1-counter automaton A. We prove the following surprising result: there exists a. 1-counter Buchi automaton A such that the cardinality of the complement L(A)(-) of the omega-language L(A) is not determined by ZFC: (1) There is a model VI of ZFC in which L (A)(-) is countable. (2) There is a model V-2 of ZFC in which L (A)(-) has cardinal 2(aleph 0). (3) There is a model V-3 of ZFC in which 1,(A)(-) has cardinal NI with aleph(0) < aleph(1) < 2(aleph 0). We prove a very similar result for the complement of an infinitary rational relation accepted by a 2-tape Buchi automaton B. As a corollary, this proves that the continuum hypothesis may be not satisfied for complements of 1-counter omega-languages and for complements of infinitary rational relations accepted by 2-tape Buchi automata. We infer from the proof of the above results that basic decision problems about 1-counter omega-languages or infinitary rational relations are actually located at the third level of the analytical hierarchy. In particular, the problem to determine whether the complement of a. 1-counter omega-language (respectively, infinitary rational relation) is countable is in Sigma(1)(3)\(Pi(1)(2) boolean OR Sigma(1)(2)). This is rather surprising if compared to the fact that it is decidable whether an infinitary rational relation is countable (respectively, uncountable).

关键词： Automata and formal languages logic in computer science computational complexity infinite words omega-languages 1-counter automaton 2-tape automaton cardinality problems decision problems analytical hierarchy largest thin effective coanalytic set models of set theory independence from the axiomatic system ZFC

来源：评论

学校读者我要写书评

暂无评论

The many faces of a translation

引用

JOURNAL OF computer AND SYSTEM scienceS 2006年第1期72卷 163-179页

作者： McKenzie, P Schwentick, T Thérien, D Vollmer, H Univ Hannover D-30167 Hannover Germany Univ Montreal Montreal PQ H3C 3J7 Canada Univ Marburg Fachbereich Math & Informat D-35032 Marburg Germany McGill Univ Sch Comp Sci Montreal PQ H3A 2A7 Canada

First-order translations have recently been characterized as the maps computed by aperiodic single-valued non-deterministic finite transducers (NFTs). It is shown here that this characterization lifts to "V-translations" and "V-single-valued-NFTs", where V is an arbitrary monoid pseudovariety that is closed under reversal. More strikingly, two-way V-transducers are introduced, and the following three models are shown exactly equivalent to Eilenberg's classical notion of a bimachine when V is a group variety or when V is the variety of aperiodic monoids: V-translations, V-single-valued-NFTs and two-way V-transducers. (c) 2005 Elsevier Inc. All rights reserved.

关键词： logic in computer science finite model theory descriptive complexity monoids automata theory

来源：评论

学校读者我要写书评

暂无评论

The complexity of the falsifiability problem for pure implicational formulas

引用

DISCRETE APPLIED MATHEMATICS 1999年 97卷 127-138页

作者： Heusch, P Univ Cologne Inst Informat D-50969 Cologne Germany

We consider Boolean formulas where logical implication (-->) is the only operator and all variables, except at most one (denoted z), occur at most twice. We show that the problem of determining falsifiability for formulas of this class is NP-complete but if the number of occurrences of z is restricted to be at most k then there is an O(\F\(k)) algorithm for certifying falsisability. We show this hierarchy of formulas, indexed on k, is interesting because even lower levels (e.g., k = 2) are not subsumed by several well-known polynomial time solvable classes of formulas. (C) 1999 Elsevier science B.V. All rights reserved.

关键词： algorithms and data structures logic in computer science

来源：评论

学校读者我要写书评

暂无评论

On the Expressive Power of Non-deterministic and Unambiguous Petri Nets over Infinite Words

引用

FUNDAMENTA INFORMATICAE 2021年第3-4期183卷 243-291页

作者： Finkel, Olivier Skrzypczak, Michal Univ Paris Sorbonne Univ CNRS Inst Math Jussieu Paris Rive Gauche Paris France Univ Warsaw Inst Informat Banacha 2 PL-02097 Warsaw Poland

We prove that omega-languages of (non-deterministic) Petri nets and omega-languages of (nondeterministic) Turing machines have the same topological complexity: the Borel and Wadge hierarchies of the class of omega-languages of (non-deterministic) Petri nets are equal to the Borel and Wadge hierarchies of the class of !-languages of (non-deterministic) Turing machines. We also show that it is highly undecidable to determine the topological complexity of a Petri net omega-language. Moreover, we infer from the proofs of the above results that the equivalence and the inclusion problems for omega-languages of Petri nets are Pi(1)(2)-complete, hence also highly undecidable. Additionally, we show that the situation is quite the opposite when considering unambiguous Petri nets, which have the semantic property that at most one accepting run exists on every input. We provide a procedure of determinising them into deterministic Muller counter machines with counter copying. As a consequence, we entail that the omega-languages recognisable by unambiguous Petri nets are Delta(0)(3) sets.

关键词： Automata and formal languages Petri nets Infinite words logic in computer science Cantor topology Borel hierarchy Wadge degrees Highly undecidable properties Unambiguous Petri nets

来源：评论

学校读者我要写书评

暂无评论

Disjunctions of Horn theories and their cores

引用

SIAM JOURNAL ON COMPUTING 2001年第1期31卷 269-288页

作者： Eiter, T Ibaraki, T Makino, K Vienna Univ Technol Inst & Ludwig Wittgenstein Lab Informat Syst A-1040 Vienna Austria Kyoto Univ Grad Sch Informat Dept Appl Math & Phys Kyoto 6068501 Japan Osaka Univ Grad Sch Engn Sci Div Syst Sci Osaka 5608531 Japan

In this paper, we study issues on disjunctions of propositional Horn theories. In particular, we consider the problems of deciding whether a disjunction of Horn theories is Horn, and, if not, computing a Horn core (i.e., a maximal Horn theory included in this disjunction) and the Horn envelope (i.e., the minimum Horn theory including the disjunction), where a Horn core and the Horn envelope are important approximations of the original theory in artificial intelligence. The problems are investigated for two different representations of Horn theories, namely, for Horn conjunctive normal forms (CNFs) and characteristic models. While the problems are shown to be intractable in general, in the case of bounded disjunctions, we present polynomial time algorithms for testing the Horn property in both representations and for computing a Horn core in the CNF representation. Even in the case of bounded disjunction, no polynomial algorithm exists (unless P=NP) for computing a Horn core in the characteristic model representation. Computing the Horn envelope is polynomial in the characteristic model representation, while it is exponential in the CNF representation, even for bounded disjunction.

关键词： computational issues in artificial intelligence logic in computer science Horn theory

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：