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

The complexity of equality constraint languages

THEORY OF COMPUTING SYSTEMS 2008年第2期43卷 136-158页

作者： Bodirsky, Manuel Kara, Jan Humboldt Univ Algorithms & Complex Dept Berlin Germany Charles Univ Prague Fac Math & Phys Dept Appl Math Prague Czech Republic

We classify the computational complexity of all constraint satisfaction problems where the constraint language is preserved by all permutations of the domain. A constraint language is preserved by all permutations of the domain if and only if all the relations in the language can be defined by boolean combinations of the equality relation. We call the corresponding constraint languages equality constraint languages. For the classification result we apply the universal-algebraic approach to infinite-valued constraint satisfaction, and show that an equality constraint language is tractable if it admits a constant unary polymorphism or an injective binary polymorphism, and is NP-complete otherwise. We also discuss how to determine algorithmically whether a given constraint language is tractable.

关键词： constraint satisfaction logic in computer science computational complexity clones on infinite domains

来源：评论

学校读者我要写书评

暂无评论

ON THE COMPLEXITY OF THE MODEL CHECKING PROBLEM

引用

SIAM JOURNAL ON COMPUTING 2018年第3期47卷 769-797页

作者： Madelaine, Florent R. Martin, Barnaby D. Univ Clermont Auvergne LIMOS F-63001 Clermont Ferrand France Univ Caen Normandie GREYC F-14000 Caen France Univ Paris Est LACL F-94010 Creteil France Univ Durham Sch Engn & Comp Sci Durham DH1 3LE England

The complexity of the model checking problem for various fragments of fi rst-order logic (FO) has attracted much attention over the last two decades, in particular for the fragment induced by (sic) and Lambda and that induced by (sic), and Lambda, which are better known as the constraint satisfaction problem and the quantified constraint satisfaction problem, respectively. The former was conjectured to follow a dichotomy between P and NP-complete by Feder and Vardi [SIAM J. Comput., 28 (1998), pp. 57{104]. For the latter, there are several partial trichotomy results between P, NP-complete, and Pspace-complete, and Chen [Meditations on quantified constraint satisfaction, in logic and Program Semantics, Springer, Heidelberg, 2012, pp. 35{49] ventured a conjecture regarding Pspace-completeness vs. membership in NP in the presence of constants. We give a comprehensive account of the whole fi eld of the complexity of model checking similar syntactic fragments of FO. The above two fragments are in fact the only ones for which there is currently no known complexity classi fi cation. Indeed, we consider all other similar syntactic fragments of FO, induced by the presence or absence of quanti fi ers and connectives, and fully classify the complexities of the parameterization of the model-checking problem by a fi nite model D, that is, the expression complexities for certain fi nite D. Perhaps surprisingly, we show that for most of these fragments, "tractability" is witnessed by a generic solving algorithm which uses quanti fi er relativization. Our classi fi cation methodology relies on tailoring suitably the algebraic approach pioneered by Jeavons, Cohen, and Gyssens [J. ACM, 44 (1997), pp. 527{548] for the constraint satisfaction problem and by Borner et al. [Inform. and Comput., 207 (2009), pp. 923{944] for the quanti fi ed constraint satisfaction problem. Most fragments under consideration can be relatively easily classi fi ed, either directly or using Schaefer's dichoto

关键词： Galois connection quanti fi ed constraints universal algebra computational complexity logic in computer science

来源：评论

学校读者我要写书评

暂无评论

An approach from answer set programming to decision making in a railway interlocking system

引用

REVISTA DE LA REAL ACADEMIA DE CIENCIAS EXACTAS FISICAS Y NATURALES SERIE A-MATEMATICAS 2014年第2期108卷 973-987页

作者： Roanes-Lozano, Eugenio Antonio Alonso, Jose Hernando, Antonio Univ Complutense Madrid IMI Dept Algebra Madrid Spain Univ Seville Dept Ciencias Comp & Inteligencia Artificial Seville Spain Univ Politecn Madrid Dept Sistemas Inteligentes Aplicados Madrid Spain

Railway interlocking systems are apparatuses that prevent conflicting movements of trains through an arrangement of tracks. A railway interlocking system takes into consideration the position of the switches (of the turnouts) and only allows trains to be given clear signals if the routes to be used by the trains are disjoint. There are many different approaches to automate decision making in railway interlocking systems (i.e., to automate supervising that the proposed situation is safe). Meanwhile the classic approaches are offline: only certain routes are allowed and their compatibility is decided in advance, our approaches take the decision on real time, so performance is key. We had previously developed Maple implementations of models based on matrix, algebraic (Grobner bases), logic and logic-algebraic approaches. They are independent from the topology of the layout and can be applied to small or medium size layouts. In this paper another completely new model (also independent from the topology of the layout), that directly translates the decision problem into logic programming, is presented. This new approach directly translates the problem in answer set programming (ASP) style, by defining relations and derived relations, from which the problem is solved using logic techniques inherent to ASP. The main procedure analyses the safety of a proposed situation and an auxiliary procedure returns, if they exist, the sections where a collision could take place. This declarative approach turns out to be much faster and efficient than the previous ones by these authors, and therefore can be applied to much bigger layouts.

关键词： Railway interlocking systems logic programming logic in computer science Mathematical modeling

来源：评论

学校读者我要写书评

暂无评论

The Rabin index of parity games: Its complexity and approximation

引用

INFORMATION AND COMPUTATION 2015年 245卷 36-53页

作者： Huth, Michael Kuo, Jim Huan-Pu Piterman, Nir Univ London Imperial Coll Sci Technol & Med Dept Comp 180 Queens Gate London SW7 2AZ England Univ Leicester Dept Comp Sci Leicester LE1 7RH Leics England

We study the descriptive complexity of parity games by taking into account the coloring of their game graphs whilst ignoring their ownership structure. Colorings of game graphs are identified if they determine the same winning regions and strategies, for all ownership structures of nodes. The Rabin index of a parity game is the minimum of the maximal color taken over all equivalent coloring functions. We show that deciding whether the Rabin index is at least k is in P for k = 1 but NP-hard for all fixed k >= 2. We present an EXPTIME algorithm that computes the Rabin index by simplifying its input coloring function. When replacing simple cycle with cycle detection in that algorithm, its output over-approximates the Rabin index in polynomial time. We evaluate this efficient algorithm as a preprocessor of solvers in detailed experiments: for Zielonka's solver on random and structured parity games and for our partial solver psolB on random games. (C) 2015 The Authors. Published by Elsevier Inc.

关键词： logic in computer science Graph theory: paths and cycles Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) Descriptive complexity and finite models Specification and verification (program logics, model checking, etc.)

来源：评论

学校读者我要写书评

暂无评论

The complexity of propositional linear temporal logics in simple cases

引用

INFORMATION AND COMPUTATION 2002年第1期174卷 84-103页

作者： Demri, S Schnoebelen, P ENS Lab Specificat & Verificat F-94235 Cachan France CNRS UMR 8643 F-94235 Cachan France

It is well known that model checking and satisfiability for PLTL are PSPACE-complete, By contrast, very little is known about whether there exist, some interesting fragments of PLTL with it lower worst-case complexity. Such results would help understand why PLTL model checkers are successfully used in practice. In this article we investigate this issue and consider model checking and satisfiability for all fragments of PLTL obtainable by restricting (1) the temporal connectives allowed. (2) the number of atomic propositions, and (3) the temporal height. (C) 2002 Elsevier science (USA).

关键词： logic in computer science computational complexity verification temporal logic model checking

来源：评论

学校读者我要写书评

暂无评论

Infinite games specified by 2-tape automata

引用

ANNALS OF PURE AND APPLIED logic 2016年第12期167卷 1184-1212页

作者： Finkel, Olivier CNRS Inst Math Jussieu Paris Rive Gauche Equipe Log Math F-75700 Paris France Univ Paris 07 F-75221 Paris 05 France Batiment Sophie Germain 58-56 Ave FranceBC 7012 F-75013 Paris France

We prove that the determinacy of Gale-Stewart games whose winning sets are infinitary rational relations accepted by 2-tape Bulchi automata is equivalent to the determinacy of (effective) analytic Gale-Stewart games which is known to be a large cardinal assumption. Then we prove that winning strategies, when they exist, can be very complex, i.e. highly non-effective, in these games. We prove the same results for Gale-Stewart games with winning sets accepted by real-time 1-counter Buchi automata, then extending previous results obtained about these games. 1. There exists a 2-tape Buchi automaton (respectively, a real-time 1-counter Buchi automaton) A such that: (a) there is a model of ZFC in which Player 1 has a winning strategy sigma in the game G(L(A)) but sigma cannot be recursive and not even in the class (Sigma U-1(2) Pi(1)(2));(b) there is a model of ZFC in which the game G(L(A)) is not determined. 2. There exists a 2-tape Buchi automaton (respectively, a real-time 1-counter Buchi automaton) A such that L(A) is an arithmetical Delta(0)(3)-set and Player 2 has a winning strategy in the game G(L(A)) but has no hyperarithmetical winning strategies in this game. 3. There exists a recursive sequence of 2-tape Buchi automata (respectively, of real-time 1-counter Buchi automata) A(n), n >= 1, such that all games G(L(A(n))) are determined, but for which it is Pi(1)(2)-complete hence highly undecidable to determine whether Player 1 has a winning strategy in the game G(L(A(n))). Then we consider the strengths of determinacy for these games, and we prove the following results. 1. There exists a 2-tape Buchi automaton (respectively, a real-time 1-counter Buchi automaton) A(#) such that the game G(A(#)) is determined iff the effective analytic determinacy holds. 2. There is a transfinite sequence of 2-tape Buchi automata (respectively, of real-time 1-counter Buchi automata) (A(alpha)), alpha

关键词： Automata and formal languages logic in computer science Gale-Stewart games 2-tape Buchi automaton 1-counter automaton Determinacy Effective analytic determinacy Models of set theory Independence from the axiomatic system ZFC Complexity of winning strategies Wadge games

来源：评论

学校读者我要写书评

暂无评论

Introducing reactive modal tableaux

引用

ANNALS OF MATHEMATICS AND ARTIFICIAL INTELLIGENCE 2012年第1-4期66卷 55-79页

作者： Gabbay, Dov Kings Coll London London WC2R 2LS England Bar Ilan Univ IL-52900 Ramat Gan Israel Univ Luxembourg Luxembourg Belgium

This paper introduces the idea of reactive semantics and reactive Beth tableaux for modal logic and quotes some of its applications. The reactive idea is very simple. Given a system with states and the possibility of transitions moving from one state to another, we can naturally imagine a path beginning at an initial state and moving along the path following allowed transitions. If our starting point is s (0), and the path is s (0), s (1),..., s (n) , then the system is ordinary non-reactive system if the options available at s (n) (i.e., which states t we can go to from s (n) ) do not depend on the path s (0),..., s (n) (i.e., do not depend on how we got to s (n) ). Otherwise if there is such dependence then the system is reactive. It seems that the simple idea of taking existing systems and turning them reactive in certain ways, has many new applications. The purpose of this paper is to introduce reactive tableaux in particular and illustrate and present some of the applications of reactivity in general. Mathematically one can take a reactive system and turn it into an ordinary system by taking the paths as our new states. This is true but from the point of view of applications there is serious loss of information here as the applicability of the reactive system comes from the way the change occurs along the path. In any specific application, the states have meaning, the transitions have meaning and the paths have meaning. Therefore the changes in the system as we go along a path can have very important meaning in the context, which enhances the usability of the model.

关键词： Modal logic Other nonclassical logic Combined logics logic in computer science Beth tableaux

来源：评论

学校读者我要写书评

暂无评论

Incompleteness Theorems, Large Cardinals, and Automata Over Finite Words

引用

INTERNATIONAL JOURNAL OF FOUNDATIONS OF computer science 2019年第3期30卷 449-467页

作者： Finkel, Olivier CNRS Inst Math Jussieu Paris Rive Gauche F-75205 Paris 13 France Univ Paris Diderot UFR Math Case 7012 F-75205 Paris 13 France

We prove that one can construct various kinds of automata over finite words for which some elementary properties are actually independent from strong set theories like T-n=: ZFC + "There exist (at least) n inaccessible cardinals", for integers n >= 0. In particular, we prove independence results for languages of finite words generated by context-free grammars, or accepted by 2-tape or 1-counter automata. Moreover we get some independence results for weighted automata and for some related finitely generated subsemigroups of the set Z(3x3)of 3-3 matrices with integer entries. Some of these latter results are independence results from the Peano axiomatic system PA.

关键词： Automata and formal languages logic in computer science finite words context-free grammars 2-tape automaton post correspondence problem weighted automaton finitely generated matrix subsemigroups of Z(3x3) models of set theory incompleteness theorems large cardinals inaccessible cardinals independence from the axiomatic system "ZFC plus there exist n inaccessible cardinals" independence from Peano arithmetic

来源：评论

学校读者我要写书评

暂无评论

THE DETERMINACY OF CONTEXT-FREE GAMES

引用

JOURNAL OF SYMBOLIC logic 2013年第4期78卷 1115-1134页

作者： Finkel, Olivier CNRS Inst Math Jussieu Paris Rive Gauche UMR 7586 Equipe Log Math F-75205 Paris 13 France Univ Paris Diderot Paris 7 F-75205 Paris 13 France

We prove that the determinacy of Gale-Stewart games whose winning sets are accepted by real-time 1-counter Buchi automata is equivalent to the determinacy of (effective) analytic Gale-Stewart games which is known to be a large cardinal assumption. We show also that the determinacy of Wadge games between two players in charge of omega-languages accepted by 1-counter Buchi automata is equivalent to the (effective) analytic Wadge determinacy. Using some results of set theory we prove that one can effectively construct a 1-counter Buchi automaton A and a Buchi automaton B such that: (1) There exists a model of ZFC in which Player 2 has a winning strategy in the Wadge game W(L(A), L(B));(2) There exists a model of ZFC in which the Wadge game W (L(A), L(B)) is not determined. Moreover these are the only two possibilities, i.e. there are no models of ZFC in which Player 1 has a winning strategy in the Wadge game W(L(A), L(B)).

关键词： Automata and formal languages logic in computer science Gale-Stewart games Wadge games determinacy effective analytic determinacy context-free games 1-counter automaton models of set theory independence from the axiomatic system ZFC

来源：评论

学校读者我要写书评

暂无评论

Introducing reactive Kripke semantics and arc accessibility

引用

ANNALS OF MATHEMATICS AND ARTIFICIAL INTELLIGENCE 2012年第1-4期66卷 7-53页

作者： Gabbay, D. Kings Coll London London WC2R 2LS England Bar Ilan Univ Ramat Gan Israel Univ Luxembourg Luxembourg Luxembourg

Ordinary Kripke models are not reactive. When we evaluate (test/ measure) a formula A at a model m, the model does not react, respond or change while we evaluate. The model is static and unchanged. This paper studies Kripke models which react to the evaluation process and change themselves during the process. The additional device we add to Kripke semantics to make it reactive is to allow the accessibility relation to access itself. Thus the accessibility relation of a reactive Kripke model contains not only pairs of possible worlds (b is accessible to a, i.e., there is an accessibility arc from a to b) but also pairs of the form , meaning that the arc (a,b) is accessible to t, or even connections of the form . This new kind of Kripke semantics allows us to characterise more axiomatic modal logics (with one modality ) by a class of reactive frames. There are logics which cannot be characterised by ordinary frames but which can be characterised by reactive frames. We also discuss the manifestation of the 'reactive' idea in the context of automata theory, where we allow the automaton to react and change it's own definition as it responds to input, and in graph theory, where the graph can change under us as we manipulate it.

关键词： Modal logic Other nonclassical logic Combined logics logic in computer science

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：