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

POLISHNESS OF SOME TOPOLOGIES RELATED TO WORD OR TREE AUTOMATA

logicAL METHODS IN computer science 2019年第2期15卷 9:1-9:21页

作者： Carton, Olivier Finkel, Olivier Lecomte, Dominique Univ Paris Diderot Inst Rech Informat Fondamentale UMR 8243 Case 7014 F-75205 Paris 13 France

We prove that the Buchi topology and the automatic topology are Polish. We also show that this cannot be fully extended to the case of the space of infinite labelled binary trees;in particular the Buchi and the Muller... 详细信息

关键词： Automata and formal languages logic in computer science infinite words Buchi automaton regular omega-language Cantor space finer topologies Buchi topology automatic topology Polish topology space of infinite labelled binary trees Buchi tree automaton Muller tree automaton

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

CLOSED SETS AND OPERATORS THEREON: REPRESENTATIONS, COMPUTABILITY AND COMPLEXITY

引用

logicAL METHODS IN computer science 2018年第2期14卷

作者： Roesnick-Neugebauer, Carsten Tech Univ Darmstadt Darmstadt Germany

The TTE approach to Computable Analysis is the study of so-called representations (encodings for continuous objects such as reals, functions, and sets) with respect to the notions of computability they induce. A rich variety of such representations had been devised over the past decades, particularly regarding closed subsets of Euclidean space plus subclasses thereof (like compact subsets). In addition, they had been compared and classified with respect to both non-uniform computability of single sets and uniform computability of operators on sets. In this paper we refine these investigations from the point of view of computational complexity. Benefiting from the concept of second-order representations and complexity recently devised by Kawamura & Cook (2012), we determine parameterized complexity bounds for operators such as union, intersection, projection, and more generally function image and inversion. By indicating natural parameters in addition to the output precision, we get a uniform view on results by Ko (1991-2013), Braverman (2004/05) and Zhao & Muller (2008), relating these problems to the P/UP/NP question in discrete complexity theory.

关键词： computational complexity logic in computer science

来源：评论

学校读者我要写书评

暂无评论

Incompleteness Theorems, Large Cardinals, and Automata over Finite Words 14th

Incompleteness Theorems, Large Cardinals, and Automata over ...

引用

14th Annual Conference on Theory and Applications of Models of Computation (TAMC)

作者： Finkel, Olivier CNRS Inst Math Jussieu Paris Rive Gauche Paris France Univ Paris 07 Paris France

ISBN: (纸本)9783319559117;9783319559100

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

来源：评论

学校读者我要写书评

暂无评论

An independent axiomatisation for free short-circuit logic

引用

Journal of Applied Non-Classical logics 2018年第1期28卷 35-71页

作者： Ponse, Alban Staudt, Daan J. C. Section Theory of Computer Science Informatics Institute Faculty of Science University of Amsterdam Amsterdam Netherlands

Short-circuit evaluation denotes the semantics of propositional connectives in which the second argument is evaluated only if the first argument does not suffice to determine the value of the expression. Free short-circuit logic is the equational logic in which compound statements are evaluated from left to right, while atomic evaluations are not memorised throughout the evaluation, i.e. evaluations of distinct occurrences of an atom in a compound statement may yield different truth values. We provide a simple semantics for free short-circuit logic (SCL) and an independent axiomatisation. Finally, we discuss evaluation strategies, some other SCLs, and side effects. © 2018, © 2018 Informa UK Limited, trading as Taylor & Francis Group.

关键词： conditional composition logic in computer science non-commutative conjunction sequential connectives short-circuit evaluation side effect

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

A note on the size of prenex normal forms

引用

INFORMATION PROCESSING LETTERS 2016年第7期116卷 443-446页

作者： Harwath, Frederik Goethe Univ Frankfurt Inst Informat Postfach 11 19 32 D-60054 Frankfurt Germany

The textbook method for converting a first-order logic formula to prenex normal form potentially leads to an exponential growth of the formula size, if the formula is allowed to use all of the classical logical connectives Lambda, boolean OR, ->, <->, sic This note presents a short proof which shows that the conversion is possible with polynomial growth of the formula size. (C) 2016 Elsevier B.V. All rights reserved.

关键词： Algorithms Formal methods logic in computer science Formula size and succinctness

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Incompleteness Theorems, Large Cardinals, and Automata over Infinite Words 42nd

Incompleteness Theorems, Large Cardinals, and Automata over ...

引用

42nd International Colloquium on Automata, Languages and Programming (ICALP)

作者： Finkel, Olivier CNRS Inst Math Jussieu Paris Rive Gauche Paris France Univ Paris 07 Paris France

ISBN: (纸本)9783662476666;9783662476659

We prove that there exist some 1-counter Buchi automata A(n) forwhich some elementary properties are independent of theories like T-n =: ZFC + "There exist (at least) n inaccessible cardinals", for integers n >= 1. In particular, if Tn is consistent, then "L(A(n)) is Borel", "L(A(n)) is arithmetical", "L(A(n)) is omega-regular", "L(A(n)) is deterministic", and "L(A(n)) is unambiguous" are provable from ZFC + "There exist (at least) n + 1 inaccessible cardinals" but not from ZFC + " There exist (at least) n inaccessible cardinals". We prove similar results for infinitary rational relations accepted by 2-tape Buchi automata.

关键词： Automata and formal languages logic in computer science Infinite words 1-counter Buchi automaton 2-tape Buchi automaton Models of set theory Incompleteness theorems Large cardinals Inaccessible cardinals Independence from the axiomatic system "ZFC plus there exist n inaccessible cardinals"

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：