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

International Conference on Numerical Analysis and Applied Mathematics (ICNAAM)

作者： Madeira, Alexandre Neves, Renato Martins, Manuel A. Barbosa, Luis S. INESC TEC HASLab Oporto Portugal Univ Minho P-4719 Braga Portugal Univ Aveiro Dept Math CIDMA Aveiro Portugal

ISBN: (纸本)9780735412873

Dynamic logic combines logic with programs, which at a certain level of abstraction, can be regarded as behaviours changing the system state and, therefore, the truth value of formulas. This paper suggests a method for generating such logics for the domain of robot controllers and illustrates it with a logic for handling resource consumption.

关键词： logic in computer science Dynamic logic Robotics

来源：评论

学校读者我要写书评

暂无评论

AMBIGUITY OF ω-LANGUAGES OF TURING MACHINES

引用

logicAL METHODS IN computer science 2014年第3期10卷

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

An omega-language is a set of infinite words over a finite alphabet X. We consider the class of recursive omega-languages, i.e. the class of omega-languages accepted by Turing machines with a Buchi acceptance condition, which is also the class Sigma(1)(1) of (effective) analytic subsets of X-omega for some finite alphabet X. We investigate here the notion of ambiguity for recursive omega-languages with regard to acceptance by Buchi Turing machines. We first present in detail essentials on the literature on omega-languages accepted by Turing Machines. Then we give a complete and broad view on the notion of ambiguity and unambiguity of Buchi Turing machines and of the omega-languages they accept. To obtain our new results, we make use of results and methods of effective descriptive set theory.

关键词： Automata and formal languages infinite words Turing machines Buchi transition systems ambiguity degrees of ambiguity logic in computer science effective descriptive set theory models of set theory

来源：评论

学校读者我要写书评

暂无评论

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 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

来源：评论

学校读者我要写书评

暂无评论

Data log and constraint satisfaction with infinite templates

引用

JOURNAL OF computer AND SYSTEM scienceS 2013年第1期79卷 79-100页

作者： Bodirsky, Manuel Dalmau, Victor Ecole Polytech CNRS LIX F-91128 Palaiseau France Univ Pompeu Fabra Barcelona Spain

On finite structures, there is a well-known connection between the expressive power of Data log, finite variable logics, the existential pebble game, and bounded hypertree duality. we study this connection for infinite structures. This has applications for constraint satisfaction with infinite templates. If the template Gamma is omega-categorical, we present various equivalent characterizations of those Gamma such that the constraint satisfaction problem (CSP) for Gamma can be solved by a Data log program. We also show that CSP(Gamma) can be solved in polynomial time for arbitrary omega-categorical structures Gamma if the input is restricted to instances of bounded treewidth. Finally, we characterize those omega-categorical templates whose CSP has Datalog width 1, and those whose CSP has strict Datalog width k. (C) 2012 Elsevier Inc. All rights reserved.

关键词： logic in computer science Computational complexity Constraint satisfaction Datalog Countably categorical structures

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

The Determinacy of Context-Free Games

The Determinacy of Context-Free Games

引用

29th International Symposium on Theoretical Aspects of computer science (STACS)

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

ISBN: (纸本)9783939897354

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 e (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: (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 context-free games

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：