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

ACTA INFORMATICA 2022年第1期59卷 125-162页

作者： Baxter, James Ribeiro, Pedro Cavalcanti, Ana Univ York Dept Comp Sci York N Yorkshire England

Specifying budgets and deadlines using a process algebra like CSP requires an explicit notion of time. The tock-CSP encoding embeds a rich and flexible approach for modelling discrete-time behaviours with powerful tool support. It uses an event tock, interpreted to mark passage of time. Analysis, however, has traditionally used the standard semantics of CSP, which is inadequate for reasoning about timed refinement. The most recent version of the model checker FDR provides tailored support for tock-CSP, including specific operators, but the standard semantics remains inadequate. In this paper, we characterise tock-CSP as a language in its own right, rich enough to model budgets and deadlines, and reason about Zeno behaviour. We present the first sound tailored semantic model for tock-CSP that captures timewise refinement. It is fully mechanised in Isabelle/HOL and, to enable use of FDR4 to check refinement in this novel model, we use model shifting, which is a technique that explicitly encodes refusals in traces.

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

来源：评论

学校读者我要写书评

暂无评论

引用

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.

来源：评论

学校读者我要写书评

暂无评论

Infinitely repeated quantum games and strategic efficiency

引用

QUANTUM information PROCESSING 2021年第12期20卷 1-24页

作者： Ikeda, Kazuki Aoki, Shoto Univ Saskatchewan Dept Math & Stat Saskatoon SK S7N 5E6 Canada Univ Saskatchewan Ctr Quantum Topol & Its Applicat QuanTA Saskatoon SK S7N 5E6 Canada Osaka Univ Dept Phys Toyonaka Osaka 5600043 Japan

Repeated quantum game theory addresses long-term relations among players who choose quantum strategies. In the conventional quantum game theory, single-round quantum games or at most finitely repeated games have been widely studied;however, less is known for infinitely repeated quantum games. Investigating infinitely repeated games is crucial since finitely repeated games do not much differ from single-round games. In this work, we establish the concept of general repeated quantum games and show the Quantum Folk Theorem, which claims that by iterating a game one can find an equilibrium strategy of the game and receive reward that is not obtained by a Nash equilibrium of the corresponding single-round quantum game. A significant difference between repeated quantum prisoner's dilemma and repeated classical prisoner's dilemma is that the classical Pareto optimal solution is not always an equilibrium of the repeated quantum game when entanglement is sufficiently strong. When entanglement is sufficiently strong and reward is small, mutual cooperation cannot be an equilibrium of the repeated quantum game. In addition, we present several concrete equilibrium strategies of the repeated quantum prisoner's dilemma.

关键词： Quantum information Technology Spintronics Quantum Computing data structures and information theory Quantum Physics Mathematical Physics

来源：评论

学校读者我要写书评

暂无评论

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.

关键词： Algorithm Analysis and Problem Complexity theory of Computation Mathematics of Computing Algorithms Computer Systems Organization and Communication Networks data structures and information theory

来源：评论

学校读者我要写书评

暂无评论

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.

来源：评论

学校读者我要写书评

暂无评论

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.

来源：评论

学校读者我要写书评

暂无评论

Montgomery-friendly primes and applications to cryptography

引用

JOURNAL OF CRYPTOGRAPHIC ENGINEERING 2021年第4期11卷 399-415页

作者： Bajard, Jean Claude Duquesne, Sylvain Sorbonne Univ Inst Math Jussieu Paris Rive Gauche CNRS INRIA F-75005 Paris France Univ Rennes 1 CNRS IRMAR F-35000 Rennes France

This paper deals with Montgomery-friendly primes designed for the modular reduction algorithm of Montgomery. These numbers are scattered in the literature and their properties are partially exploited. We exhibit a large family of Montgomery-friendly primes which give rise to efficient modular reduction algorithms. We develop two main outcomes. The first one is dedicated directly to cryptography, in particular for isogeny-based approaches and more generally to elliptic curves cryptography (ECC). We suggest more appropriate finite fields and curves in terms of complexity for the recommended security levels, for both isogeny-based cryptography and ECC. The second issue is mainly arithmetic (even if its main use is cryptography), and we propose families of alternative RNS bases. We show that, for dedicated architectures with word operators, we can reach, for a same or better complexity, larger RNS bases with Montgomery-friendly pairwise co-primes than the RNS bases generally used in the literature with pseudo-Mersenne numbers.

关键词： Cryptology Circuits and Systems Computer Communication Networks Communications Engineering Networks data structures and information theory Operating Systems

来源：评论

学校读者我要写书评

暂无评论

A longitudinal exploratory study on code smells in server side web applications

引用

SOFTWARE QUALITY JOURNAL 2021年第4期29卷 901-941页

作者： Bessghaier, Narjes Ouni, Ali Mkaouer, Mohamed Wiem Univ Quebec ETS Montreal Montreal PQ Canada Rochester Inst Technol Rochester NY 14623 USA

Modern web applications have become one of the largest parts of the current software market over years, bringing cross-platform compatibility and data integration advantages that encouraged businesses to shift toward their adoption. Like any software application, code smells can be manifested as violations of implementation and design standards which could impact the maintainability, comprehensibility and performance of web applications. While there have been extensive studies on traditional code smells recently, little knowledge is available on code smells in web-based applications (web apps). As web applications are split into their client and server sides, we present in this study a first step in exploring the code smells diffuseness and effect on the server side of web applications. To this end, we conduct an exploratory study on a total of 430 releases from 10 long-lived open-source web-based applications on 12 common code smell types. We aim to better understand and gain insights into the diffuseness of code smells, their co-occurrences and effects on the change- and fault-proneness in server side code. Our study delivers several important findings. First, code smells are not equally diffused in web apps server side, among which smells related to complex, and large code components display high diffuseness and frequency rates. Second, the co-occurrence phenomenon is highly common, but the association degree between code smell pairs is weak. Code smells related to large size and high complexity exhibit a higher degree of co-occurrences. Third, smelly files are more likely to change than smell-free files, whereas not all smell types are likely to cause equal change sizes in the code base. Fourth, smelly files are more vulnerable to faults than smell-free files, and 86% of smelly files are more likely to manifest more faults than other files. Hence, developers should be aware of the existence of code smells in their web applications and consider detecting and refa

关键词： Software Engineering/Programming and Operating Systems Programming Languages Compilers Interpreters data structures and information theory Operating Systems

来源：评论

学校读者我要写书评

暂无评论

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.

来源：评论

学校读者我要写书评

暂无评论

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.

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：