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

Proof techniques in Membrane Computing

THEORETICAL COMPUTER SCIENCE 2021年 862卷 236-249页

作者： Orellana-Martin, David Valencia-Cabrera, Luis Perez-Jimenez, Mario J. Univ Seville Dept Comp Sci & Artificial Intelligence Res Grp Nat Comp ETSI Informat Avda Reina Mercedes S-N Seville 41012 Spain

From the creation of the field of Membrane Computing in 1998, several research lines have been opened. On the one hand, theoretical questions like the computational power and the computational efficiency of P systems have been studied. In this sense, several techniques to demonstrate the ability of these systems to provide solutions to computational problems have been explored. The study of efficient(polynomial-time) solutions to presumably hard problems for finding thin frontiers of efficiency is a very active area. On the other hand, several applications in biology, ecology, economy, robotics and fault diagnosis, among others, have been investigated. Real systems with some characteristics seem to be easy to model with membrane systems due to their behaviour. In this work, a survey of the theoretical part will be given, explaining techniques both in the field of computability theory and in the field of computational complexity theory. (C) 2020 Elsevier B.V. All rights reserved.

关键词： Membrane Computing Computability theory computational complexity theory

来源：评论

学校读者我要写书评

暂无评论

Traversing graphs in small space

引用

IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS 2000年第3期E83D卷 392-396页

作者： Toda, S Nihon Univ Coll Humanities & Sci Dept Appl Math Tokyo 1568550 Japan

We sketch two algorithms that solve the undirected st-connectivity problem in a small amount of space. One is due to Nisan, Szemeredy and Wigderson, and takes space O(log(3)/(2) n), where n denotes the number of nodes in a give undirected graph. This is the first algorithm that overcame the Savitch barrier on the space complexity of the problem. The other is due to Tarui and this author, and takes space O(sw(G)(2) log(2) n), where sw(G) denotes the separation-width of a given graph G. Their result implies that the st-connectivity problem can be solved in logarithmic space for any class of graphs with separation-width bounded above by a predetermined constant. This: class is one of few nontrivial classes for which the st-connectivity problem can be solved in logarithmic space.

关键词： st-connectivity problem logarithmic space graph algorithm randomization computational complexity theory

来源：评论

学校读者我要写书评

暂无评论

Local Restrictions from the Furst-Saxe-Sipser Paper

引用

theory OF COMPUTING SYSTEMS 2017年第1期60卷 20-32页

作者： Tamaki, Suguru Watanabe, Osamu Kyoto Univ Sakyo Ku Kyoto 6068501 Japan Tokyo Inst Technol Tokyo 1528552 Japan

In their celebrated paper (Furst et al., Math. Syst. theory 17(1), 13-27 (12)), Furst, Saxe, and Sipser used random restrictions to reveal the weakness of Boolean circuits of bounded depth, establishing that constant-depth and polynomial-size circuits cannot compute the parity function. Such local restrictions have played important roles and have found many applications in complexity analysis and algorithm design over the past three decades. In this article, we give a brief overview of two intriguing applications of local restrictions: the first one is for the Isomorphism Conjecture and the second one is for moderately exponential time algorithms for the Boolean formula satisfiability problem.

关键词： Local restriction Random restriction computational complexity theory Algorithm design

来源：评论

学校读者我要写书评

暂无评论

Optimal series-parallel trade-offs for reducing a function to its own graph

引用

INFORMATION AND COMPUTATION 2002年第2期173卷 123-131页

作者： Beigel, R Hemaspaandra, LA Hempel, H Vogel, J Univ Rochester Dept Comp Sci Rochester NY 14627 USA NEC Res Inst Princeton NJ 08540 USA Univ Jena Inst Informat D-07743 Jena Germany Temple Univ Coll Sci & Technol Dept Informat & Comp Sci Philadelphia PA 19122 USA Univ Illinois Chicago IL USA Univ Wurzburg Wurzburg Germany Univ Rochester Rochester NY 14627 USA Le Moyne Coll Syracuse NY 13214 USA RIT Rochester NY USA

Consider the problem of computing a function given only an oracle for its graph. For this problem, we present optimal trade-offs between serial and parallel queries. In particular, we give a function for which paralle... 详细信息

关键词： computational complexity theory polynomial-time reductions series-parallel trade-offs graphs of functions

来源：评论

学校读者我要写书评

暂无评论

Minimal cooperation as a way to achieve the efficiency in cell-like membrane systems

引用

JOURNAL OF MEMBRANE COMPUTING 2019年第2期1卷 85-92页

作者： Orellana-Martin, David Valencia-Cabrera, Luis Riscos-Nunez, Agustin Perez-Jimenez, Mario J. Univ Seville Dept Comp Sci & Artificial Intelligence Res Grp Nat Comp Avda Reina Mercedes S-N Seville 41012 Spain

Cooperation is doubtless a relevant ingredient on rewriting rules based computing models. This paper provides an overview on both classical and newest results studying how cooperation among objects influences the ability of cell-like membrane systems to solve computationally hard problems in an efficient way. In this paper, two types of such membrane systems will be considered: (a) polarizationless P systems with active membranes without dissolution rules when minimal cooperation is permitted in object evolution rules;and (b) cell-like P systems with symport/antiport rules of minimal length. Specifically, assuming that P is not equal to NP, several frontiers of the efficiency are obtained in these two computing frameworks, in such manner that each borderline provides a tool to tackle the P versus NP problem.

关键词： Minimal cooperation Cell-like P systems computational complexity theory

来源：评论

学校读者我要写书评

暂无评论

HYPERMEDIA AND RANDOMIZED ALGORITHMS FOR MEDICAL EXPERT SYSTEMS

引用

COMPUTER METHODS AND PROGRAMS IN BIOMEDICINE 1990年第1期32卷 5-16页

作者： CHAVEZ, RM COOPER, GF Section on Medical Informatics Stanford University School of Medicine CA 94305.

KNET is an environment for constructing probabilistic, knowledge-intensive systems within the axiomatic framework of decision theory. The KNET architecture defines a complete separation between the hypermedia user interface on the one hand, and the representation and management of expert opinion on the other. KNET offers a choice of algorithms for probabilistic inference. We and our coworkers have used KNET to build consultation systems for lymph-node pathology, bone-marrow transplantation therapy, clinical epidemiology, and alarm management in the intensive-care unit. Most important, KNET contains a randomized approximation scheme (RAS) for the difficult and almost certainly intractable problem of Bayesian inference. Our algorithm can, in many circumstances, perform efficient approximate inference in large and richly interconnected models of medical diagnosis. In this article, we describe the architecture of KNET, construct a randomized algorithm for probabilistic inference, and analyze the algorithm's performance. Finally, we characterize our algorithms' empiric behavior and explore its potential for parallel speedups. From design to implementation, then, KNET demonstrates the crucial interaction between theoretical computer science and medical informatics.

关键词： Probabilistic expert system computational complexity theory Randomized algorithm Medical informatics

来源：评论

学校读者我要写书评

暂无评论

Gaps, Ambiguity, and Establishing complexity-Class Containments via Iterative Constant-Setting

引用

ACM TRANSACTIONS ON COMPUTATION theory 2024年第4期16卷 1-26页

作者： Hemaspaandra, Lane A. Juvekar, Mandar Nadjimzadah, Arian Phillips, Patrick A. Univ Rochester Rochester NY 14627 USA Boston Univ Dept Comp Sci Boston MA 02215 USA UCLA Dept Math Los Angeles CA 90095 USA Gen Dynam Corp Reston VA 20190 USA

Cai and Hemachandra used iterative constant-setting to prove that Few c (R) P (and thus that FewP c (R) P). In this article, we note that there is a tension between the nondeterministic ambiguity of the class one is seeking to capture, and the density (or, to be more precise, the needed "nongappiness") of the easy-to-find "targets" used in iterative constant-setting. In particular, we show that even less restrictive gap-size upper bounds regarding the targets allow one to capture ambiguity-limited classes. Through a flexible, metatheorembased approach, we do so for a wide range of classes including the logarithmic-ambiguity version of Valiant's unambiguous nondeterminism class UP. Our work lowers the bar for what advances regarding the existence of infinite, P-printable sets of primes would suffice to show that restricted counting classes based on the primes have the power to accept superconstant-ambiguity analogues of UP. As an application of our work, we prove that the Lenstra-Pomerance-Wagstaff Conjecture implies that all (O(1) + log log n )-ambiguity NP sets are in the restricted counting class RC PRIMES .

关键词： Structural complexity theory computational complexity theory ambiguity-limited NP restricted counting classes P-printable sets

来源：评论

学校读者我要写书评

暂无评论

Seeking computational efficiency boundaries: the Pun's conjecture

引用

JOURNAL OF MEMBRANE COMPUTING 2020年第4期2卷 323-331页

作者： Orellana-Martin, David Riscos-Nunez, Agustin Univ Sevilla ETSI Informat Dept Comp Sci & Artificial Intelligence Res Grp Nat Comp Avda Reina Mercedes S-N Seville 41012 Spain

In 2005, Gh. Pun raised an interesting question concerning the role of electrical charges in P systems with active membranes from a complexity point of view. Specifically, he formulated a question about the computational efficiency of polarizationless P systems with dissolution rules and division rules only for elementary membranes. Several approaches have been carried out, and some partial answers have been given. This is probably the most important open problem in computational complexity theory in the framework of Membrane Computing. The study of the efficiency of membrane systems has been a very fruitful area, providing not only the above-stated partial answers, but also several frontiers of efficiency to tackle the P vs NP problem. In this work, a survey on classical and current results on complexity aspects is given, emphasizing on the frontiers of efficiency and the ingredients taken into account for each of them.

关键词： Pun's conjecture Membrane computing computational complexity theory P systems MSC 68Q10 MSC 68Q15

来源：评论

学校读者我要写书评

暂无评论

Voting-based ensemble learning for partial lexicographic preference forests over combinatorial domains

引用

ANNALS OF MATHEMATICS AND ARTIFICIAL INTELLIGENCE 2019年第1-2期87卷 137-155页

作者： Liu, Xudong Truszczynski, Miroslaw Univ North Florida Sch Comp Jacksonville FL 32224 USA Univ Kentucky Dept Comp Sci Lexington KY 40506 USA

We study preference representation models based on partial lexicographic preference trees (PLP-trees). We propose to represent preference relations as forests of small PLP-trees (PLP-forests), and to use voting rules to aggregate orders represented by the individual trees into a single order to be taken as a model of the agent's preference relation. We show that when learned from examples, PLP-forests have better accuracy than single PLP-trees. We also show that the choice of a voting rule does not have a major effect on the aggregated order, thus rendering the problem of selecting the "right" rule less critical. Next, for the proposed PLP-forest preference models, we develop methods to compute optimal and near-optimal outcomes, the tasks that appear difficult for some other common preference models. Lastly, we compare our models with those based on decision trees, which brings up questions for future research.

关键词： Lexicographic preference models Preference learning Preference modeling and reasoning Social choice theory computational complexity theory Voting theory Maximum satisfiability

来源：评论

学校读者我要写书评

暂无评论

A solution to the only one object problem with dissolution rules

引用

JOURNAL OF MEMBRANE COMPUTING 2024年第2期6卷 1-8页

作者： Caselmann, Julien Orellana-Martin, David Humboldt Univ Berlin Germany Univ Seville Dept Comp Sci & Artificial Intelligence Res Grp Nat Comp Avda Reina Mercedes S-N Seville 41012 Spain Univ Seville SCORE Lab I3US Avda Reina Mercedes S-N Seville 41012 Spain

In the framework of membrane computing, (non-)uniform families of recognizer membrane systems are usually defined to solve abstract decision problems. In this sense, the use of finite resources for each member of the family makes the difference with respect to Turing machines solving these problems. While keeping the finite nature of these systems, it is interesting to know which type of problems can be solved by means of a single membrane system. For this purpose, the complexity class PMC R 1 p \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{PMC}<^>{1p}_{\mathcal {R}}$$\end{document} was defined as the class of problems that can be solved by means of a single membrane system in polynomial time. Due to the polynomial-time encoding of the input, at least all the problems from P can be solved with a trivial system. To go below P, the class PMC R 1 f \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{PMC}<^>{1f}_{\mathcal {R}}$$\end{document} restricts the definition of this encoding. In this work, we study the capability of different types of membrane systems to solve the ONLY-ONE-OBJECT problem, while having the encoding restriction.

关键词： Membrane computing computational complexity theory Only one object problem

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：