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

HIERARCHY AND CLOSURE-PROPERTIES OF VARIOUS CLASSES OF TAG-systems

ACTA INFORMATICA 1983年第2期20卷 179-196页

作者： PANSIOT, JJ Centre de Calcul de l'Esplanade Université Louis Pasteur 7 rue René Descartes F-67084 Strasbourg Cédex France

We define sets of infinite words generated by various classes of tag-systems. We show that every infinite word generated by extended tag-system can also be generated by ɛ-free tag-system. We give a full inclusion grap... 详细信息

关键词： Logics and Meanings of Programs computer systems organization and communication networks Software Engineering/Programming and Operating systems Data Structures and Information Theory Theory of Computation Information systems and communication Service

来源：评论

学校读者我要写书评

暂无评论

A #SAT Algorithm for Small Constant-Depth Circuits with PTF gates

引用

ALGORITHMICA 2022年第4期84卷 1132-1162页

作者： Bajpai, Swapnam Krishan, Vaibhav Kush, Deepanshu Limaye, Nutan Srinivasan, Srikanth Indian Inst Technol Dept Comp Sci & Engn Mumbai Maharashtra India Indian Inst Technol Dept Math Mumbai Maharashtra India

We show that there is a better-than-brute-force algorithm that, when given a small constant-depth Boolean circuit C made up of gates that compute constant-degree Polynomial Threshold functions or PTFs (i.e., Boolean functions that compute signs of constant-degree polynomials), counts the number of satisfying assignments to C in significantly better than brute-force time. Formally, for any constants d, k, there is an epsilon > 0 such that the zero-error randomized algorithm counts the number of satisfying assignments to a given depth-d circuit C made up of k-PTF gates such that C has at most n(1+epsilon) many wires. The algorithm runs in time 2(n-n Omega(epsilon)). Before our result, no algorithm for beating brute-force search was known for counting the number of satisfying assignments even for a single degree-k PTF (which is a depth-1 circuit with linearly many wires).We give two different algorithms for the case of a single PTF. The first uses a learning algorithm for learning degree-1 PTFs (or Linear Threshold Functions) using comparison queries due to Kane, Lovett and Moran (STOC 2018), and the second uses a proof of Hofmeister (COCOON 1996) for converting a degree-1 PTF to a depth-two threshold circuit with small weights. We show that both these ideas fit nicely into a memoization approach that yields the #SAT algorithms.

关键词： Algorithm Analysis and Problem Complexity Theory of Computation Mathematics of Computing Algorithms computer systems organization and communication networks Data Structures and Information Theory

来源：评论

学校读者我要写书评

暂无评论

Equilibria for games with combined qualitative and quantitative objectives

引用

ACTA INFORMATICA 2021年第6期58卷 585-610页

作者： Gutierrez, Julian Murano, Aniello Perelli, Giuseppe Rubin, Sasha Steeples, Thomas Wooldridge, Michael Monash Univ Melbourne Vic Australia Univ Naples Federico II Naples Italy Sapienza Univ Rome Rome Italy Univ Sydney Sydney NSW Australia Univ Oxford Oxford England

The overall aim of our research is to develop techniques to reason about the equilibrium properties of multi-agent systems. We model multi-agent systems as concurrent games, in which each player is a process that is assumed to act independently and strategically in pursuit of personal preferences. In this article, we study these games in the context of finite-memory strategies, and we assume players' preferences are defined by a qualitative and a quantitative objective, which are related by a lexicographic order: a player first prefers to satisfy its qualitative objective (given as a formula of linear temporal logic) and then prefers to minimise costs (given by a mean-payoff function). Our main result is that deciding the existence of a strict epsilon Nash equilibrium in such games is 2ExpTime-complete (and hence decidable), even if players' deviations are implemented as infinite-memory strategies.

来源：评论

学校读者我要写书评

暂无评论

Lower bounds for searching robots, some faulty

引用

DISTRIBUTED COMPUTING 2021年第4期34卷 229-237页

作者： Kupavskii, Andrey Welzl, Emo Moscow Inst Phys & Technol Dolgoprudnyi Russia Univ Birmingham Birmingham W Midlands England Swiss Fed Inst Technol Dept Comp Sci Zurich Switzerland

Suppose we are sending out k robots from 0 to search the real line at constant speed (with turns) to find a target at an unknown location;f of the robots are faulty, meaning that they fail to report the target although visiting its location (called crash type). The goal is to find the target in time at most lambda|x|, if the target is located at x, |x| >= 1, for lambda as small as possible. We show that this cannot be achieved for lambda < 2 rho(rho)/(rho-1)(rho-1) +1, rho:=2(f+1)/k, which is tight due to earlier work (see Czyzowitz et al. in Proc PODC'16, pp 405-414, 2016, where this problem was introduced). This also gives some better than previously known lower bounds for so-called Byzantine-type faulty robots that may actually wrongly report a target. In the second part of the paper we deal with the m-rays generalization of the problem, where the hidden target is to be detected on m rays all emanating at the same point. Using a generalization of our methods, along with a useful relaxation of the original problem, we establish a tight lower for this setting as well (as above, with rho :=(m(f+1)k)). When specialized to the case f = 0, this resolves the question on parallel search on m rays, posed by three groups of scientists some 15-30 years ago: by Baeza-Yates, Culberson, and Rawlins;by Kao, Ma, Sipser, and Yin;and by Bernstein, Finkelstein, and Zilberstein. The m-rays generalization is known to have connections to other, seemingly unrelated, problems, including hybrid algorithms for on-line problems, and so-called contract algorithms.

关键词： computer communication networks computer Hardware computer systems organization and communication networks Software Engineering/Programming and Operating systems Theory of Computation

来源：评论

学校读者我要写书评

暂无评论

Approximation Algorithm for Vertex Cover with Multiple Covering Constraints

引用

ALGORITHMICA 2022年第1期84卷 1-12页

作者： Hung, Eunpyeong Kao, Mong-Jen Natl Taiwan Univ Dept Comp Sci & Informat Engn Taipei Taiwan Natl Yang Ming Chiao Tung Univ Dept Comp Sci Hsinchu Taiwan

We consider the vertex cover problem with multiple coverage constraints in hypergraphs. In this problem, we are given a hypergraph G = (V, E) with a maximum edge size f, a cost function w : V -> Z(+), and edge subsets P-1, - P-2, ..., P-r of E along with covering requirements k(1), k(2), ..., k(r) for each subset. The objective is to find a minimum cost subset S of V such that, for each edge subset P-i, at least k(i) edges of it are covered by S. This problem is a basic yet general form of classical vertex cover problem and the edge-partitioned vertex cover problem considered by Bera et al. We present a primal-dual algorithm yielding an (f . H-r + H-r)-approximation for this problem, where H-r is the rth harmonic number. This improves over the previous ratio of (3cf log r ), where c is a large constant used to ensure a low failure probability for Monte-Carlo randomized algorithms. Compared to the previous result, our algorithm is deterministic and pure combinatorial, meaning that no Ellipsoid solver is required for this basic problem. Our result can be seen as a novel reinterpretation of a few classical tight results using the language of LP primal-duality.

来源：评论

学校读者我要写书评

暂无评论

MinMax algorithms for stabilizing consensus

引用

DISTRIBUTED COMPUTING 2021年第3期34卷 195-206页

作者： Charron-Bost, Bernadette Moran, Shlomo Ecole Polytech CNRS F-91128 Palaiseau France Technion Dept Comp Sci IL-32000 Haifa Israel

In the stabilizing consensus problem each agent of a networked system has an input value and is repeatedly writing an output value;it is required that eventually all the output values stabilize to the same value which, moreover, must be one of the input values. We study this problem for a synchronous model with identical and anonymous agents that are connected by a time-varying topology and may join the system at any time (asynchronous start). Our main result is a generic MinMax algorithm that solves the stabilizing consensus problem in this model when, in each sufficiently long but bounded period of time, there is an agent, called a root, that can send messages, possibly indirectly, to all other agents. We stress that the bound on the time required for achieving this rootedness property is unknown to the agents. Such topologies are highly dynamic (in particular, roots may change arbitrarily over time) and may have very weak connectivity properties (an agent may be never a root). Our distributed MinMax algorithms thus require neither central control nor any global information and are also quite efficient in terms of message size and storage requirements.

关键词： computer communication networks computer Hardware computer systems organization and communication networks Software Engineering/Programming and Operating systems Theory of Computation

来源：评论

学校读者我要写书评

暂无评论

Opening up new vistas on Advanced Multimedia Content Processing - Preface

引用

NEW GENERATION COMPUTING 2000年第4期18卷 295-303页

作者： Nishio, S Osaka Univ Grad Sch Engn Dept Informat Syst Engn Suita Osaka 5650871 Japan

The remarkable advances made in computer and communication hard-ware/software system technologies have made it possible for us to usemultime- dia data for many purposes in various service *** the importance of developing an advanced processingenvironment for the acquisition, manage- ment, retrieval, creation,and utilization of large amounts of multimedia content, the authorhas been conducting the "Advanced Multimedia Content Processing(AMCP)" research project on Japan since 1997, focusing on themanagement of the continuous and semistructured features ofmultimedia content.

关键词： Artificial Intelligence computer Hardware computer systems organization and communication networks Software Engineering/Programming and Operating systems

来源：评论

学校读者我要写书评

暂无评论

引用

ACTA INFORMATICA 2021年第5期58卷 529-569页

作者： Gorrieri, Roberto Univ Bologna Dipartimento Informat Sci & Ingn Mura A Zamboni 7 I-40127 Bologna Italy

BPP nets, a subclass of finite Place/Transition Petri nets, are equipped with an efficiently decidable, truly concurrent, bisimulation-based, behavioral equivalence, calledteam bisimilarity. This equivalence is a very intuitive extension of classic bisimulation equivalence (over labeled transition systems) to BPP nets and it is checked in a distributed manner, without necessarily building a global model of the overall behavior of the marked BPP net. An associated distributed modal logic, calledteam modal logic(TML, for short), is presented and shown to be coherent with team bisimilarity: two markings are team bisimilar if and only if they satisfy the same TML formulae. As the process algebra BPP (with guarded summation and guarded body of constants) is expressive enough to represent all and only the BPP nets, we provide algebraic laws for team bisimilarity as well as a finite, sound and complete, axiomatization.

来源：评论

学校读者我要写书评

暂无评论

Finite automata with undirected state graphs

引用

ACTA INFORMATICA 2022年第1期59卷 163-181页

作者： Kutrib, Martin Malcher, Andreas Schneider, Christian Univ Giessen Inst Informat Arndtstr 2 D-35392 Giessen Germany

We investigate finite automata whose state graphs are undirected. This means that for any transition from state p to q consuming some letter a from the input there exists a symmetric transition from state q to p consuming a letter a as well. So, the corresponding language families are subregular, and in particular in the deterministic case, subreversible. In detail, we study the operational descriptional complexity of deterministic and nondeterministic undirected finite automata. To this end, the different types of automata on alphabets with few letters are characterized. Then, the operational state complexity of the Boolean operations as well as the operations concatenation and iteration is investigated, where tight upper and lower bounds are derived for unary as well as arbitrary alphabets under the condition that the corresponding language classes are closed under the operation considered.

来源：评论

学校读者我要写书评

暂无评论

A note on slack enforcement mechanisms for self-suspending tasks

引用

REAL-TIME systems 2021年第4期57卷 387-396页

作者： Guenzel, Mario Chen, Jian-Jia TU Dortmund Univ Dept Informat Dortmund Germany

This paper provides counterexamples for the slack enforcement mechanisms to handle segmented self-suspending real-time tasks by Lakshmanan and Rajkumar (Proceedings of the Real-Time and Embedded Technology and Applica... 详细信息

关键词： computer systems organization and communication networks communications Engineering networks Special Purpose and Application-Based systems Performance and Reliability Control Robotics Mechatronics

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：