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

Indecision and delays are the parents of failure-taming them algorithmically by synthesizing delay-resilient control

引用

ACTA INFORMATICA 2021年第5期58卷 497-528页

作者： Chen, Mingshuai Fraenzle, Martin Li, Yangjia Mosaad, Peter N. Zhan, Naijun Rhein Westfal TH Aachen Lehrstuhl Informat 2 Aachen Germany Carl von Ossietzky Univ Oldenburg Dept Comp Sci Oldenburg Germany Univ Tartu Tartu Estonia Chinese Acad Sci Inst Software State Key Lab Comp Sci Beijing Peoples R China Univ Chinese Acad Sci Beijing Peoples R China

The possible interactions between a controller and its environment can naturally be modelled as the arena of a two-player game, and adding an appropriate winning condition permits to specify desirable behavior. The classical model here is the positional game, where both players can (fully or partially) observe the current position in the game graph, which in turn is indicative of their mutual current states. In practice, neither sensing and actuating the environment through physical devices nor data forwarding to and from the controller and signal processing in the controller are instantaneous. The resultant delays force the controller to draw decisions before being aware of the recent history of a play and to submit these decisions well before they can take effect asynchronously. It is known that existence of a winning strategy for the controller in games with such delays is decidable over finite game graphs and with respect to omega regular objectives. The underlying reduction, however, is impractical for non-trivial delays as it incurs a blow-up of the game graph which is exponential in the magnitude of the delay. For safety objectives, we propose a more practical incremental algorithm successively synthesizing a series of controllers handling increasing delays and reducing the game-graph size in between. It is demonstrated using benchmark examples that even a simplistic explicit-state implementation of this algorithm outperforms state-of-the-art symbolic synthesis algorithms as soon as non-trivial delays have to be handled. We furthermore address the practically relevant cases of non-order-preserving delays and bounded message loss, as arising in actual networked control, thereby considerably extending the scope of regular game theory under delay.

关键词： 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

来源：评论

学校读者我要写书评

暂无评论

Finding and Counting Permutations via CSPs

引用

ALGORITHMICA 2021年第8期83卷 2552-2577页

作者： Berendsohn, Benjamin Aram Kozma, Laszlo Marx, Daniel Free Univ Berlin Inst Informat Berlin Germany Max Planck Inst Informat Saarland Informat Campus Saarbrucken Germany

Permutation patterns and pattern avoidance have been intensively studied in combinatorics and computer science, going back at least to the seminal work of Knuth on stack-sorting (1968). Perhaps the most natural algorithmic question in this area is deciding whether a given permutation of length n contains a given pattern of length k. In this work we give two new algorithms for this well-studied problem, one whose running time is n (k/4+o(k)), and a polynomial-space algorithm whose running time is the better of O(1.618(n)) and O(n(k/2+1)). These results improve the earlier best bounds of n(0)(.)(47k)(+o(k)) and O(1.79(n)) due to Ahal and Rabinovich (2000) resp. Bruner and Lackner (2012) and are the fastest algorithms for the problem when k is an element of Omega(log n). We show that both our new algorithms and the previous exponential-time algorithms in the literature can be viewed through the unifying lens of constraint-satisfaction. Our algorithms can also count, within the same running time, the number of occurrences of a pattern. We show that this result is close to optimal: solving the counting problem in time f(k).n(o(k/logk)) would contradict the exponential-time hypothesis (ETH). For some special classes of patterns we obtain improved running times. We further prove that 3-increasing (4321-avoiding) and 3-decreasing (1234-avoiding) permutations can, in some sense, embed arbitrary permutations of almost linear length, which indicates that a sub-exponential running time is unlikely with the current techniques, even for patterns from these restricted classes.

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

来源：评论

学校读者我要写书评

暂无评论

TuringMobile: a turing machine of oblivious mobile robots with limited visibility and its applications

引用

DISTRIBUTED COMPUTING 2022年第2期35卷 105-122页

作者： Di Luna, Giuseppe A. Flocchini, Paola Santoro, Nicola Viglietta, Giovanni Sapienza Univ Rome DIAG Via Ariosto 25 Rome Italy Univ Ottawa Sch Elect Engn & Comp Sci 800 King Edward Ave Ottawa ON Canada Carleton Univ Sch Comp Sci 1125 Colonel By Dr Ottawa ON Canada JAIST Sch Informat Sci 1-1 Asahidai Nomi City Ishikawa 9231211 Japan

In this paper we investigate the computational power of a set of mobile robots with limited visibility. At each iteration, a robot takes a snapshot of its surroundings, uses the snapshot to compute a destination point, and it moves toward its destination. Robots are punctiform and memoryless, they operate in Rm, they have local reference systems independent of each other, and are activated asynchronously by an adversarial scheduler. Moreover, robots are non-rigid, in that they may be stopped by the scheduler at each move before reaching their destination (but are guaranteed to travel at least a fixed unknown distance before being stopped). We show that despite these strong limitations, it is possible to arrange 3m + 3k of these weak entities in R-m to simulate the behavior of a stronger robot that is rigid (i.e., it always reaches its destination) and is endowed with k registers of persistent memory, each of which can store a real number. We call this arrangement a TuringMobile. In its simplest form, a TuringMobile consisting of only three robots can travel in the plane and store and update a single real number. We also prove that this task is impossible with fewer than three robots. Among the applications of the TuringMobile, we focused on Near-Gathering (all robots have to gather in a small-enough disk) and Pattern Formation (of which Gathering is a special case) with limited visibility. Interestingly, our investigation implies that both problems are solvable in Euclidean spaces of any dimension, even if the visibility graph of the robots is initially disconnected, provided that a small amount of these robots are arranged to form a TuringMobile. In the special case of the plane, a basic TuringMobile of only three robots is sufficient.

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

来源：评论

学校读者我要写书评

暂无评论

Producing Genomic Sequences after Genome Scaffolding with Ambiguous Paths: Complexity, Approximation and Lower Bounds

引用

ALGORITHMICA 2021年第7期83卷 2063-2095页

作者： Davot, Tom Chateau, Annie Giroudeau, Rodolphe Weller, Mathias Tabary, Dorine CNRS UMR 5506 LIRMM Montpellier France LIGM CNRS Paris France MIPS EA 2332 Mulhouse France

Scaffolding is the final step in assembling Next Generation Sequencing data, in which pre-assembled contiguous regions ("contigs") are oriented and ordered using information that links them (for example, mapping of paired-end reads). As the genome of some species is highly repetitive, we allow placing some contigs multiple times, thereby generalizing established computational models for this problem. We study the subsequent problems induced by the translation of solutions of the model back to actual sequences, proposing models and analyzing the complexity of the resulting computational problems. We find both polynomial-time and NP-hard special cases like planarity or bounded degree. Finally, we propose two polynomial-time approximation algorithms according to cut/weight score.

来源：评论

学校读者我要写书评

暂无评论

Improved distributed Δ-coloring

引用

DISTRIBUTED COMPUTING 2021年第4期34卷 239-258页

作者： Ghaffari, Mohsen Hirvonen, Juho Kuhn, Fabian Maus, Yannic Swiss Fed Inst Technol Zurich Switzerland Aalto Univ Espoo Finland Univ Freiburg Freiburg Germany Technion Haifa Israel

We present a randomized distributed algorithm that computes a Delta-coloring in any non-complete graph with maximum degree Delta >= 4 in O(log Delta)+ 2(O)(root(log log n)) rounds, as well as a randomized algorithm that computes a Delta-coloring in O((log log n)(2)) rounds when Delta is an element of [3, O(1)]. Both these algorithms improve on an O(log(3) n/log Delta)-round algorithm of Panconesi and Srinivasan (STOC'93), which has remained the state of the art for the past 25 years. Moreover, the latter algorithm gets (exponentially) closer to an Omega (log log n) round lower bound of Brandt et al. (STOC'16).

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

来源：评论

学校读者我要写书评

暂无评论

Near Isometric Terminal Embeddings for Doubling Metrics

引用

ALGORITHMICA 2021年第11期83卷 3319-3337页

作者： Elkin, Michael Neiman, Ofer Ben Gurion Univ Negev Dept Comp Sci Beer Sheva Israel

Given a metric space (X, d), a set of terminals K subset of X, and a parameter 0 < epsilon < 1, we consider metric structures (e.g., spanners, distance oracles, embedding into normed spaces) that preserve distances for all pairs in K x X up to a factor of 1 + epsilon, and have small size (e.g. number of edges for spanners, dimension for embeddings). While such terminal (aka source-wise) metric structures are known to exist in several settings, no terminal spanner or embedding with distortion close to 1, is currently known. Here we devise such terminal metric structures for doubling metrics, and show that essentially any metric structure with distortion 1 + epsilon and space s(vertical bar X vertical bar) has its terminal counterpart, with distortion 1 + O(epsilon) and space s(vertical bar K vertical bar) + n. In particular, for any doubling metric on n points, a set of k terminals, and constant 0 < epsilon < 1, there exists A spanner with stretch 1 + epsilon for pairs in K x X, with n + O(k) edges. A labeling scheme with stretch 1 + epsilon for pairs in K x X, with label size approximate to log k. An embedding into l(infinity)(d) with distortion 1 + epsilon for pairs in K x X, where d = O(log k). Moreover, surprisingly, the last two results apply if only the metric space on K is doubling, while the metric on X can be arbitrary.

来源：评论

学校读者我要写书评

暂无评论

Session-based concurrency, declaratively

引用

ACTA INFORMATICA 2022年第1期59卷 35-87页

作者： Cano, Mauricio Lopez, Hugo A. Perez, Jorge A. Rueda, Camilo Univ Groningen Groningen Netherlands Univ Copenhagen Copenhagen Denmark DCR Solut AS Copenhagen Denmark CWI Amsterdam Netherlands Pontificia Univ Javeriana Cali Valle Del Cauca Colombia

Session-based concurrency is a type-based approach to the analysis of message-passing programs. These programs may be specified in an operational or declarative style: the former defines how interactions are properly structured;the latter defines governing conditions for correct interactions. In this paper, we study rigorous relationships between operational and declarative models of session-based concurrency. We develop a correct encoding of session pi-calculus processes into the linear concurrent constraint calculus (lcc), a declarative model of concurrency based on partial information (constraints). We exploit session types to ensure that our encoding satisfies precise correctness properties and that it offers a sound basis on which operational and declarative requirements can be jointly specified and reasoned about. We demonstrate the applicability of our results by using our encoding in the specification of realistic communication patterns with time and contextual information.

来源：评论

学校读者我要写书评

暂无评论

A New Lower Bound for Classic Online Bin Packing

引用

ALGORITHMICA 2021年第7期83卷 2047-2062页

作者： Balogh, Janos Bekesi, Jozsef Dosa, Gyorgy Epstein, Leah Levin, Asaf Univ Szeged Inst Informat Szeged Hungary Univ Pannonia Dept Math Veszprem Hungary Univ Haifa Dept Math Haifa Israel Technion Fac Ind Engn & Management Haifa Israel

We improve the lower bound on the asymptotic competitive ratio of any online algorithm for bin packing to above 1.54278. We demonstrate for the first time the advantage of branching and the applicability of full adaptivity in the design of lower bounds for the classic online bin packing problem. We apply a new method for weight based analysis, which is usually applied only in proofs of upper bounds. The values of previous lower bounds were approximately 1.5401 and 1.5403.

来源：评论

学校读者我要写书评

暂无评论

Complement for two-way alternating automata

引用

ACTA INFORMATICA 2021年第5期58卷 463-495页

作者： Geffert, Viliam Kapoutsis, Christos A. Zakzok, Mohammad Safarik Univ Dept Comp Sci Kosice Slovakia Carnegie Mellon Univ Qatar Dept Comp Sci Doha Qatar

We consider the problem of converting a two-way alternating finite automaton (2AFA) with n states to a 2AFA accepting the complement of its language. Complementing is trivial for halting2AFAs, by swapping the roles of existential and universal decisions and the roles of accepting and rejecting states. However, since 2AFAs do not have resources to detect infinite loops by counting executed steps, it was not known whether the cost of complementing is polynomial in n in the general case. Here we shall show that 2AFAs can be complemented by using O(n(7)) states.

来源：评论

学校读者我要写书评

暂无评论

A New Lower Bound for Deterministic Truthful Scheduling

引用

ALGORITHMICA 2021年第9期83卷 2895-2913页

作者： Giannakopoulos, Yiannis Hammerl, Alexander Pocas, Diogo Friedrich Alexander Univ Erlangen Nurnberg FAU Erlangen Germany Tech Univ Munich Munich Germany Univ Lisbon LASIGE Fac Ciencias Lisbon Portugal

We study the problem of truthfully scheduling m tasks to n selfish unrelated machines, under the objective of makespan minimization, as was introduced in the seminal work of Nisan and Ronen (in: The 31st Annual ACM symposium on Theory of Computing (STOC), 1999). Closing the current gap of [2.618, n] on the approximation ratio of deterministic truthful mechanisms is a notorious open problem in the field of algorithmic mechanism design. We provide the first such improvement in more than a decade, since the lower bounds of 2.414 (for n = 3) and 2.618 (for n -> infinity) by Christodoulou et al. (in: Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2007) and Koutsoupias and Vidali (in: Proceedings of Mathematical Foundations of computer Science (MFCS), 2007), respectively. More specifically, we show that the currently best lower bound of 2.618 can be achieved even for just n = 4 machines;for n = 5 we already get the first improvement, namely 2.711;and allowing the number of machines to grow arbitrarily large we can get a lower bound of 2.755.

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：