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

15th International Workshop on Logical and Semantic Frameworks, with applications (LSFA)

作者： Brodo, Linda Olarte, Carlos Univ Sassari Sassari Italy Univ Fed Rio Grande do Norte ECT Natal RN Brazil

Multiparty interactions are common place in today's distributed systems. An agent usually communicates, in a single session, with other agents to accomplish a given task. Take for instance an online transaction including the vendor, the client, the credit card system and the bank. When specifying this kind of system, we probably observe a single transaction including several (binary) communications leading to changes in the state of all the involved agents. Multiway synchronization process calculi, that move from a binary to a multiparty synchronization discipline, have been proposed to formally study the behavior of those systems. However, adopting models such as Bodei, Brodo, and Bruni's Core Network algebra (CNA), where the number of participants in an interaction is not fixed a priori, leads to an exponential blow-up in the number of states/behaviors that can be observed from the system. In this paper we explore mechanisms to tackle this problem. We extend CNA with constraints that declaratively allow the modeler to restrict the interaction that should actually happen. Our extended process algebra, called CCNA, finds application in balancing the interactions in a concurrent system, leading to a simple, deadlock-free and fair solution for the Dinning Philosopher problem. Our definition of constraints is general enough and it offers the possibility of accumulating costs in a multiparty negotiation. Hence, only computations respecting the thresholds imposed by the modeler are observed. We use this machinery to neatly model a Service Level Agreement protocol. We develop the theory of CCNA including its operational semantics and a behavioral equivalence that we prove to be a congruence. We also propose a prototypical implementation that allows us to verify, automatically, some of the systems explored in the paper.

关键词： Concurrency theory constraints multiparty interactions

来源：评论

学校读者我要写书评

暂无评论

Revisit the Partial Coloring Method: Prefix Spencer and Sampling

arXiv

引用

arXiv 2024年

作者： Cai, Dongrun Chen, Xue Shu, Wenxuan Wang, Haoyu Zou, Guangyi University of Science and Technology of China China College of Computer Science University of Science and Technology of China Hefei230026 China Hefei National Laboratory University of Science and Technology of China Hefei230088 China

As the most powerful tool in discrepancy theory, the partial coloring method has wide applications in many problems including the Beck-Fiala problem [BF81] and Spencer’s celebrated result [Spe85, Ban10, LM12, Rot17]. Currently, there are two major algorithmic approaches for the partial coloring method: the first approach uses linear algebraic tools to update the partial coloring for many rounds [Ban10, LM12, BG17, LRR17, BDGL19];and the second one, called Gaussian measure algorithm [Rot17, RR23], projects a random Gaussian vector to the feasible region that satisfies all discrepancy constraints in [−1, 1]n. In this work, we explore the advantages of these two approaches and show the following results for them separately. 1. Spencer [Spe86] conjectured that the prefix discrepancy of any A ∈ {0, 1}m×n is O(√m), i.e., ∃x ∈ {±1}n such that maxt≤n k Pi≤t A(·, i) · x(i)k∞ = O(√m) where A(·, i) denotes column i of A. Combining small deviations bounds of the Gaussian processes and the Gaussian measure algorithm [Rot17], we show how to find a partial coloring with prefix discrepancy O(√m) and Ω(n) entries in {±1} efficiently. To the best of our knowledge, this provides the first partial coloring whose prefix discrepancy is almost optimal [Spe85, Spe86] (up to constants). However, unlike the classical discrepancy problem [Bec81, Spe85], there is no reduction on the number of variables n for the prefix problem. By recursively applying partial coloring, we obtain a full coloring with prefix discrepancy O(√m · log Om(n) ). Prior to this work, the best bounds of the prefix Spencer conjecture for arbitrarily large n were 2m [BG81] and O(√m log n) [Ban12, BG17]. 2. Our second result extends the first linear algebraic approach to a sampling algorithm in Spencer’s classical setting. On the first hand, besides the six deviation bound [Spe85], Spencer also proved that there are 1.99m good colorings with discrepancy O(√m) for any A ∈ {0, 1}m×m. Hence a natural question is to design effi

关键词： Linear algebra

来源：评论

学校读者我要写书评

暂无评论

POSITIVE MAPS AND ENTANGLEMENT IN REAL HILBERT SPACES

arXiv

引用

arXiv 2022年

作者： Chiribella, Giulio Davidson, Kenneth R. Paulsen, Vern I. Rahaman, Mizanur Department of Computer Science The University of Hong Kong Pok Fu Lam Road Hong Kong Department of Pure Mathematics University of Waterloo WaterlooONN2L 3G1 Canada Institute for Quantum Computing Department of Pure Mathematics University of Waterloo Waterloo WaterlooONN2L 3G1 Canada Univ Lyon ENS Lyon UCBL CNRS Inria LIP LyonCedex 07 F-69342 France

The theory of positive maps plays a central role in operator algebras and functional analysis, and has countless applications in quantum information science. The theory was originally developed for operators acting on complex Hilbert spaces, and less is known about its variant on real Hilbert spaces. In this article we study positive maps acting on a full matrix algebra over the reals, pointing out a number of fundamental differences with the complex case and discussing their implications in quantum information. We provide a necessary and sufficient condition for a real map to admit a positive complexification, and connect the existence of positive maps with non-positive complexification with the existence of mixed states that are entangled in real Hilbert space quantum mechanics, but separable in the complex version, providing explicit examples both for the maps and for the states. Finally, we discuss entanglement breaking and PPT maps, and we show that a straightforward real version of the PPT-squared conjecture is false even in dimension 2. Nevertheless, we show that the original PPT-squared conjecture implies a different conjecture for real maps, in which the PPT property is replaced by a stronger property of invariance under partial transposition (IPT). When the IPT property is assumed, we prove an asymptotic version of the conjecture. Copyright © 2022, The Authors. All rights reserved.

关键词： Hilbert spaces

来源：评论

学校读者我要写书评

暂无评论

Grobner Basis over Semigroup algebras: Algorithms and applications for Sparse Polynomial Systems 19

Grobner Basis over Semigroup Algebras: Algorithms and Applic...

引用

44th ACM International Symposium on Symbolic and algebraic Computation (ISSAC)

作者： Bender, Matias R. Faugere, Jean-Charles Tsigaridas, Elias Sorbonne Univ CNRS INRIA Lab Informat Paris 6LIP6Equipe PolSys F-75005 Paris France

ISBN: (纸本)9781450360845

Grobner bases is one the most powerful tools in algorithmic nonlinear algebra. Their computation is an intrinsically hard problem with a complexity at least single exponential in the number of variables. However, in most of the cases, the polynomial systems coming from applications have some kind of structure. We consider sparse systems where the input polynomials have a few non-zero terms. Our approach to exploit sparsity is to embed the systems in a semigroup algebra and to compute Grobner bases over this algebra. Up to now, the algorithms that follow this approach benefit from the sparsity only in the case where all the polynomials have the same sparsity structure, that is the same Newton polytope. We introduce the first algorithm that overcomes this restriction. Under regularity assumptions, it performs no redundant computations. Further, we extend this algorithm to compute Grobner basis in the standard algebra and solve sparse polynomials systems over the torus (C*)(n). The complexity of the algorithm depends on the Newton polytopes.

关键词： Grobner Basis Solving Polynomial System Mixed Sparse System Sparse Elimination theory Toric Variety Koszul Complex

来源：评论

学校读者我要写书评

暂无评论

A Class of Representations of the Orthosymplectic Lie Superalgebras$$\mathcal{B}(n,n)$$ and$$\mathcal{B}(\infty,\infty )$$ 13th

A Class of Representations of the Orthosymplectic Lie Supera...

引用

13th International Workshop on Lie theory and Its applications in Physics, LT 2019

作者： Stoilova, N.I. Van der Jeugt, J. Institute for Nuclear Research and Nuclear Energy Boul. Tsarigradsko Chaussee 72 Sofia1784 Bulgaria Department of Applied Mathematics Computer Science and Statistics Ghent University Krijgslaan 281-S9 Gent9000 Belgium

ISBN: (纸本)9789811577741

In 1982 Palev showed that the algebraic structure generated by the creation and annihilation operators of a system of m parafermions and n parabosons, satisfying the mutual parafermion relations, is the Lie superalgebra. The "parastatistics Fock spaces" of order p of such systems are then certain lowest weight representations of. We investigate now the situation when the number of parafermions and parabosons becomes infinite, which is of interest not only in a physics context but also from the mathematical point of view. In this contribution, we will discuss the various steps that are needed to understand the infinite-rank case. First, we will introduce appropriate bases and Dynkin diagrams for that allow us to extend. Then we will develop a new matrix form for, because the standard one is not appropriate for taking this limit. Following this, we construct a new Gelfand-Zetlin basis of the parastatistics Fock spaces in the finite rank case (in correspondence with this new matrix form). The new structures, related to a non-distinguished simple root system, allow the extension to. This leads to the definition of the algebra as a Lie superalgebra generated by an infinite number of creation and annihilation operators (subject to certain relations), or as an algebra of certain infinite-dimensional matrices. We study the parastatistics Fock spaces, as certain lowest weight representations of. In particular, we construct a basis consisting of well-described row-stable Gelfand-Zetlin patterns. © 2020, Springer Nature Singapore Pte Ltd.

关键词： Matrix algebra

来源：评论

学校读者我要写书评

暂无评论

Non-radial solutions for some semilinear elliptic equations on the disk

引用

NONLINEAR ANALYSIS-theory METHODS & applications 2019年 179卷 294-308页

作者： Arioli, Gianni Koch, Hans Politecn Milan Dept Math Piazza Leonardo da Vinci 92 I-20133 Milan Italy Univ Texas Austin Dept Math Austin TX 78712 USA

Starting with approximate solutions of the equation -Delta u = wu(3) on the disk, with zero boundary conditions, we prove that there exist true solutions nearby. One of the challenges here lies in the fact that we need simultaneous and accurate control of both the (inverse) Dirichlet Laplacean and nonlinearities. We achieve this with the aid of a computer, using a Banach algebra of real analytic functions, based on Zernike polynomials. Besides proving existence, and symmetry properties, we also determine the Morse index of the solutions. (C) 2018 Elsevier Ltd. All rights reserved.

关键词： Elliptic equation Symmetry computer assisted proof

来源：评论

学校读者我要写书评

暂无评论

On a class of matrices generated by certain generalized permutation matrices and applications

引用

LINEAR & MULTILINEAR algebra 2019年第10期67卷 2117-2134页

作者： Kaddoura, Issam Mourad, Bassam Lebanese Int Univ Dept Math Saida Lebanon Lebanese Univ Fac Sci Dept Math Beirut Lebanon

In this paper, we study a particular class of matrices generated by generalized permutation matrices corresponding to a subgroup of some permutation group. As applications, we first present a technique from which we can get closed formulas for the roots of many families of polynomial equations with degree between 5 and 10, inclusive. Then, we describe a tool that shows how to find solutions to Fermat's last theorem and Beal's conjecture over the square integer matrices of any dimension. Finally, simple generalizations of some of the concepts in number theory to integer square matrices are presented.

关键词： Generalized permutation matrices eigenvalues eigenvectors roots of polynomials non-negative matrices inverse eigenvalue problem matrix number theory

来源：评论

学校读者我要写书评

暂无评论

On generalized Vietoris' number sequences

引用

DISCRETE APPLIED MATHEMATICS 2019年 269卷 77-85页

作者： Cacao, Isabel Irene Falcao, M. Malonek, Helmuth R. Univ Aveiro CIDMA Ctr Res & Dev Math & Applicat Aveiro Portugal Univ Aveiro Dept Math Aveiro Portugal Univ Minho CMAT Ctr Math Minho Portugal Univ Minho Dept Math & Applicat Minho Portugal

Recently, by using methods of hypercomplex function theory, the authors have shown that a certain sequence S of rational numbers (Vietoris' sequence) combines seemingly disperse subjects in real, complex and hypercomplex analysis. This sequence appeared for the first time in a theorem by Vietoris (1958) with important applications in harmonic analysis (Askey/Steinig, 1974) and in the theory of stable holomorphic functions (Ruscheweyh/Salinas, 2004). A non-standard application of Clifford algebra tools for defining Clifford-holomorphic sequences of Appell polynomials was the hypercomplex context in which a one-parametric generalization S(n), n >= 1, of S (corresponding to n = 2) surprisingly showed up. Without relying on hypercomplex methods this paper demonstrates how purely real methods also lead to s(n). For arbitrary n >= 1 the generating function is determined and for n = 2 a particular case of a recurrence relation similar to that known for Catalan numbers is proved. (C) 2018 Elsevier B.V. All rights reserved.

关键词： Vietoris' number sequence Hypercomplex Appell polynomials Generating function Recurrence relation

来源：评论

学校读者我要写书评

暂无评论

Operator Scaling: theory and applications

引用

FOUNDATIONS OF COMPUTATIONAL MATHEMATICS 2020年第2期20卷 223-290页

作者： Garg, Ankit Gurvits, Leonid Oliveira, Rafael Wigderson, Avi Microsoft Res India Bengaluru India CUNY City Coll Dept Comp Sci New York NY USA Simons Inst Berkeley CA USA Inst Adv Study Olden Lane Princeton NJ 08540 USA

In this paper, we present a deterministic polynomial time algorithm for testing whether a symbolic matrix in non-commuting variables over Q is invertible or not. The analogous question for commuting variables is the celebrated polynomial identity testing (PIT) for symbolic determinants. In contrast to the commutative case, which has an efficient probabilistic algorithm, the best previous algorithm for the non-commutative setting required exponential time (Ivanyos et al. in Comput Complex 26(3):717-763, 2017) (whether or not randomization is allowed). The algorithm efficiently solves the "word problem" for the free skew field, and the identity testing problem for arithmetic formulae with division over non-commuting variables, two problems which had only exponential time algorithms prior to this work. The main contribution of this paper is a complexity analysis of an existing algorithm due to Gurvits (J Comput Syst Sci 69(3):448-484, 2004), who proved it was polynomial time for certain classes of inputs. We prove it always runs in polynomial time. The main component of our analysis is a simple (given the necessary known tools) lower bound on central notion of capacity of operators (introduced by Gurvits 2004). We extend the algorithm to actually approximate capacity to any accuracy in polynomial time, and use this analysis to give quantitative bounds on the continuity of capacity (the latter is used in a subsequent paper on Brascamp-Lieb inequalities). We also extend the algorithm to compute not only singularity, but actually the (non-commutative) rank of a symbolic matrix, yielding a factor 2 approximation of the commutative rank. This naturally raises a relaxation of the commutative PIT problem to achieving better deterministic approximation of the commutative rank. Symbolic matrices in non-commuting variables, and the related structural and algorithmic questions, have a remarkable number of diverse origins and motivations. They arise independently in (commutative)

关键词： Derandomization Non-commutative algebra Polynomial identity testing Invariant theory Quantum operators

来源：评论

学校读者我要写书评

暂无评论

q-Binomials and related symmetric unimodal polynomials

引用

JOURNAL OF DIFFERENCE EQUATIONS AND applications 2019年第2期25卷 262-293页

作者： Ek, Bryan Rutgers State Univ Sch Arts & Sci Dept Math Piscataway NJ 08854 USA

The q-binomial coefficients were conjectured to be unimodal as early as the 1850's but it remained unproven until Sylvester's 1878 proof using invariant theory. In 1982, Proctor gave an 'elementary' proof using linear algebra. Finally, in 1989, Kathy O'Hara provided a combinatorial proof of the unimodality of the q-binomial coefficients. Very soon thereafter, Doron Zeilberger translated the argument into an elegant recurrence. We introduce several perturbations to the recurrence to create a larger family of unimodal polynomials. We analyse how these perturbations affect the final polynomial and analyse some specific cases.

关键词： Partition unimodal dynamical programming computer-aided recursive OEIS Recurrence combinatorics

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：