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

Structural and dynamic changes in concurrent systems: Reconfigurable Petri nets

IEEE TRANSACTIONS ON COMPUTERS 2004年第9期53卷 1147-1158页

作者： Llorens, M Oliver, J Univ Politecn Valencia Dept Sistemas Informat & Computac E-46022 Valencia Spain

The aim of this work is the modeling and verification of concurrent systems subject to dynamic changes using extensions of Petri nets. We begin by introducing the notion of net rewriting system. In a net rewriting system, a system configuration is described as a Petri net and a change in configuration is described as a graph rewriting rule. We show that net rewriting systems are Turing powerful, that is, the basic decidable properties of Petri nets are lost and, thus, automatic verification in not possible for this class. A subclass of net rewriting systems are reconfigurable Petri nets. In a reconfigurable Petri net, a change in configuration amounts to the modification of the flow relations of the places in the domain of the involved rule according to this rule, independently of the context in which this rewriting applies. We show that reconfigurable Petri nets are formally equivalent to Petri nets. This equivalence ensures that all the fundamental properties of Petri nets are still decidable for reconfigurable Petri nets and this model is thus amenable to automatic verification tools. Therefore, the expressiveness of both models is the same, but, with reconfigurable Petri nets, we can easily and directly model systems that change their structure dynamically.

关键词： theory of computation computation by abstract devices models of computation relations between models modes of computation parallelism and concurrency

来源：评论

学校读者我要写书评

暂无评论

Confusion of memory

引用

INFORMATION PROCESSING LETTERS 2008年第3-4期107卷 114-119页

作者： Moss, Lawrence S. Indiana Univ Dept Math Bloomington IN 47405 USA

It is a truism that for a machine to have a useful access to memory or workspace, it must "know" where its input ends and its working memory begins. Most machine models separate input from memory explicitly, in one way or another. We are interested here in computational models which do not separate input from working memory. We study the situation on deterministic single-queue machines working on a two symbol alphabet. We establish a negative result about such machines: they cannot compute the length of their input. This confirms the intuition that such machines are "unable to tell" where on the queue the input ends and the memory begins. On the positive side, we note that there are some interesting things that one can do with such queue machines: their halting problem is undecidable, there are self-replicating machines, and there are recognizable languages outside of the control hierarchy. (C) 2008 Elsevier B.V. All rights reserved.

关键词： theory of computation models of computation formal languages

来源：评论

学校读者我要写书评

暂无评论

A Formulation of Composition for Cellular Automata on Groups

引用

IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS 2014年第3期E97D卷 448-454页

作者： Inokuchi, Shuichi Ito, Takahiro Fujio, Mitsuhiko Mizoguchi, Yoshihiro Kyushu Univ Fac Math Fukuoka 8190395 Japan TOME R&D Inc Kyoto 6008813 Japan Kinki Univ Fac Humanity Oriented Sci & Engn Iizuka Fukuoka 8208555 Japan Kyushu Univ Inst Math Ind Fukuoka 8190395 Japan

We introduce the notion of 'Composition', 'Union' and 'Division' of cellular automata on groups. A kind of notions of compositions was investigated by Sato [10] and Manzini [6] for linear cellular automata, we extend the notion to general cellular automata on groups and investigated their properties. We observe the all unions and compositions generated by one-dimensional 2-neighborhood cellular automata over Z(2) including non-linear cellular automata. Next we prove that the composition is right-distributive over union, but is not left-distributive. Finally, we conclude by showing reformulation of our definition of cellular automata on group which admit more than three states. We also show our formulation contains the representation using formal power series for linear cellular automata in Manzini [6].

关键词： cellular automata groups models of computation automata

来源：评论

学校读者我要写书评

暂无评论

A generic framework for modeling heterogeneous real-time systems

引用

COMPUTER STANDARDS & INTERFACES 2005年第1期28卷 43-58页

作者： He, H Zhong, YF Cai, CL Huazhong Univ Sci & Technol Natl CAD Support Software Engn Res Ctr Wuhan 430074 Hubei Peoples R China

Complex real-time systems usually consist of heterogeneous components. These components interact with different semantics. Modeling these systems normally need integrating several domain-specific tools such as UML, Simulink. But interchanging data between these tools is very difficult. UML is a standard modeling language for object-oriented software development, used more and more in real-time domain. It provides several extensibility mechanisms to allow modeling special domains. This paper presents a generic framework, which is based on UML notations and metamodels, for heterogeneous modeling real-time systems. So engineers from different domains can work together on a unified platform. (c) 2004 Elsevier B.V. All rights reserved.

关键词： real-time systems models of computation UML framework object-oriented

来源：评论

学校读者我要写书评

暂无评论

A lambda calculus for quantum computation

引用

SIAM JOURNAL ON COMPUTING 2004年第5期33卷 1109-1135页

作者： van Tonder, A Brown Univ Dept Phys Providence RI 02906 USA

The classical lambda calculus may be regarded both as a programming language and as a formal algebraic system for reasoning about computation. It provides a computational model equivalent to the Turing machine and continues to be of enormous benefit in the classical theory of computation. We propose that quantum computation, like its classical counterpart, may benefit from a version of the lambda calculus suitable for expressing and reasoning about quantum algorithms. In this paper we develop a quantum lambda calculus as an alternative model of quantum computation, which combines some of the benefits of both the quantum Turing machine and the quantum circuit models. The calculus turns out to be closely related to the linear lambda calculi used in the study of linear logic. We set up a computational model and an equational proof system for this calculus, and we argue that it is equivalent to the quantum Turing machine.

关键词： quantum computation lambda calculus linear logic models of computation

来源：评论

学校读者我要写书评

暂无评论

Theory versus practice in annealing-based quantum computing

引用

THEORETICAL COMPUTER SCIENCE 2020年 816卷 169-183页

作者： McGeoch, Catherine C. D Wave Syst Burnaby BC Canada

This paper introduces basic concepts of annealing-based quantum computing, also known as adiabatic quantum computing (AQC) and quantum annealing (QA), and surveys what is known about this novel computing paradigm. Extensive empirical research on physical quantum annealing processers built by D-Wave Systems has exposed many interesting features and properties. However, because of longstanding differences between abstract and empirical approaches to the study of computational performance, much of this work may not be considered relevant to questions of interest to complexity theory;by the same token, several theoretical results in quantum computing may be considered irrelevant to practical experience. To address this communication gap, this paper proposes models of computation and of algorithms that lie on a scale of instantiation between pencil-and-paper abstraction and physical device. models at intermediate points on these scales can provide a common language, allowing researchers from both ends to communicate and share their results. The paper also gives several examples of common terms that have different technical meanings in different regions of this highly multidisciplinary field, which can create barriers to effective communication across disciplines. (C) 2020 Elsevier B.V. All rights reserved.

关键词： Quantum computing Adiabatic quantum computing Quantum annealing models of computation

来源：评论

学校读者我要写书评

暂无评论

BSP versus LogP

引用

ALGORITHMICA 1999年第3-4期24卷 405-421页

作者： Bilardi, G Herley, KT Pietracaprina, A Pucci, G Spirakis, P Univ Padua Dipartimento Elettron & Informat I-35131 Padua Italy Univ Illinois Dept Elect Engn & Comp Sci Chicago IL 60607 USA Natl Univ Ireland Univ Coll Cork Dept Comp Sci Cork Ireland Comp Technol Inst GR-26110 Patras Greece

A quantitative comparison of the BSP and LogP models of parallel computation is developed. We concentrate on a variant of LogP that disallows the so-called stalling behavior, although issues surrounding the stalling phenomenon are also explored. Very efficient cross simulations between the two models are derived, showing their substantial equivalence for algorithmic design guided by asymptotic analysis. it is also shown that the two models can be implemented with similar performance on most point-to-point networks. In conclusion, within the limits of our analysis that is mainly of an asymptotic nature. BSP and (stall-free) LogP can be viewed as closely related variants within the bandwidth-latency framework for modeling parallel computation. BSP seems somewhat preferable due to its greater simplicity and portability, and slightly greater power. LogP lends itself more naturally to multiuser mode.

关键词： models of computation parallel computation bridging models portability BSP model LogP model

来源：评论

学校读者我要写书评

暂无评论

k-approximating circuits

引用

IEEE TRANSACTIONS ON COMPUTERS 2006年第7期55卷 913-917页

作者： Cadoli, M Donini, FM Liberatore, P Schaerf, M Univ Roma La Sapienza Dipartimento Informat & Sistemist I-00198 Rome Italy Univ Tuscia Fac Sci Polit I-01100 Viterbo Italy

In this paper, we define and study the k-approximating circuits. A circuit accepting a given set of inputs A is k-approximated by accepting inputs that differ from one of A by at most k bits. We show that the existenc... 详细信息

关键词： reliability and testing complexity measures and classes models of computation

来源：评论

学校读者我要写书评

暂无评论

PROBLEMS COMPLETE FOR CRPLUS-L

引用

INFORMATION PROCESSING LETTERS 1990年第5期36卷 247-250页

作者： DAMM, C Sektion Mathematik Humboldt-Universität zu Berlin PO Box 1297 DDR-1086 Berlin Germany

⊕ L is the class of languages acceptable by logarithmic space bounded Turing machines that work nondeterministically and are equipped with parity-acceptance. Several natural problems are shown to be complete for ⊕ L under NC 1 -reductions. A consequence is that ⊕ L is the 2 -analogon of Cook's class DET , the class of problems NC 1 -reducible to the computation of determinants over .

关键词： models of computation complexity classes matrices over finite fields

来源：评论

学校读者我要写书评

暂无评论

Weak models of distributed computing, with connections to modal logic

引用

DISTRIBUTED COMPUTING 2015年第1期28卷 31-53页

作者： Hella, Lauri Jarvisalo, Matti Kuusisto, Antti Laurinharju, Juhana Lempiainen, Tuomo Luosto, Kerkko Suomela, Jukka Virtema, Jonni Univ Tampere Sch Informat Sci FIN-33101 Tampere Finland Univ Helsinki Dept Comp Sci HIIT SF-00510 Helsinki Finland Univ Wroclaw Inst Comp Sci PL-51151 Wroclaw Poland

This work presents a classification of weak models of distributed computing. We focus on deterministic distributed algorithms, and study models of computing that are weaker versions of the widely-studied port-numbering model. In the port-numbering model, a node of degree d receives messages through d input ports and sends messages through d output ports, both numbered with 1, 2,..., d. In this work, VVc is the class of all graph problems that can be solved in the standard port-numbering model. We study the following subclasses of VVc: VV: Input port i and output port i are not necessarily connected to the same neighbour. MV: Input ports are not numbered;algorithms receive a multiset of messages. SV: Input ports are not numbered;algorithms receive a set of messages. VB: Output ports are not numbered;algorithms send the same message to all output ports. MB: Combination of MV and VB. SB: Combination of SV and VB. Now we have many trivial containment relations, such as SB subset of MB subset of VB subset of VV subset of VVc, but it is not obvious if, for example, either of VB subset of SV or SV subset of VB should hold. Nevertheless, it turns out that we can identify a linear order on these classes. We prove that SB (sic) MB = VB (sic) SV = MV = VV (sic) VVc. The same holds for the constant-time versions of these classes. We also show that the constant-time variants of these classes can be characterised by a corresponding modal logic. Hence the linear order identified in this work has direct implications in the study of the expressibility of modal logic. Conversely, one can use tools from modal logic to study these classes.

关键词： Distributed computing Local algorithms Modal logic models of computation

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：