We present a language L which is recognizable by a probabilistic finite automaton (PFA) with probability 1 - epsilon for all epsilon > 0 with O(log(2) n) states, with a deterministic finite automaton (DFA) with 0(n...
详细信息
ISBN:
(数字)9783540361374
ISBN:
(纸本)354000145X
We present a language L which is recognizable by a probabilistic finite automaton (PFA) with probability 1 - epsilon for all epsilon > 0 with O(log(2) n) states, with a deterministic finite automaton (DFA) with 0(n) states, but a quantum finite automaton (QFA) needs at least 2(Omega(n/ log n)) states.
this paper presents a parallel artificial immune system designed for graph coloring. the algorithm is based on the clonal selection principle. Each processor operates on its own pool of antibodies and a migration mech...
详细信息
ISBN:
(数字)9783540775669
ISBN:
(纸本)9783540775652
this paper presents a parallel artificial immune system designed for graph coloring. the algorithm is based on the clonal selection principle. Each processor operates on its own pool of antibodies and a migration mechanism is used to allow processors to exchange information. Experimental results show that migration improves the performance of the algorithm. the experiments were performed using a high performance cluster on a set of well-established graph instances available on the Web.
this proceedings contains 14 papers. ACSC 2015 focuses on all fields of computerscience research and topics include: Algorithms Logic and Logic Programming;Artificial Intelligence Mobile Computing;Communications and ...
ISBN:
(纸本)9781921770418
this proceedings contains 14 papers. ACSC 2015 focuses on all fields of computerscience research and topics include: Algorithms Logic and Logic Programming;Artificial Intelligence Mobile Computing;Communications and Networks Multimedia;Compilers Natural Language;computer Architecture Object-Oriented Systems;computer Vision Operating Systems;Computational Geometry Pattern Matching and Image Processing;Concurrency Persistence;Databases Programming Languages;Data Structures Real-time Systems;Distributed Systems;Reliability;E-Commerce;Robotics;Education Security;Embedded Systems;Scientific Computing;Fault Tolerance Simulation;Forensic Computing Software Engineering;Formal Methods Speech;Functional Programming theory;Graphics Trusted Systems;High Performance Computing Visualization;Human-computer Interaction, etc. the key terms of this proceedings include compressive sensing, software engineering methods, cryptocurrency, generic entity, fusing polarity, directional bias, HMM modelling, SCADA network mapping, Botnet detection, pedagogical tool.
Clinical guidelines and decision support systems (DSS) play an important role in daily practices of medicine. Many text-based guidelines have been encoded for work-flow simulation of DSS to automate health care. Durin...
详细信息
ISBN:
(纸本)9781450342056
Clinical guidelines and decision support systems (DSS) play an important role in daily practices of medicine. Many text-based guidelines have been encoded for work-flow simulation of DSS to automate health care. During the collaboration with Carle hospital to develop a DSS, we identify that, for some complex and life-critical diseases, it is highly desirable to automatically rigorously verify some complex temporal properties in guidelines, which brings new challenges to current simulation based DSS with limited support of automatical formal verification and real-time data analysis. In this paper, we conduct the first study on applying runtime verification to cooperate withcurrent DSS based on real-time data. Within the proposed technique, a user-friendly domain specific language, named DRTV, is designed to specify vital real-time data sampled by medical devices and temporal properties originated from clinical guidelines. Some interfaces are developed for data acquisition and communication. then, for medical practice scenarios described in DRTV model, we will automatically generate event sequences and runtime property verifier automata. If a temporal property violates, real-time warnings will be produced by the formal verifier and passed to medical DSS. We have used DRTV to specify different kinds of medical care scenarios, and applied the proposed technique to assist existing DSS. As presented in experiment results, in terms of warning detection, it outperforms the only use of DSS or human inspection, and improves the quality of clinical health care of hospital.
We define two-dimensional rational automata for pictures as an extension of classical finite automata for strings. they are obtained replacing the finite relation computed by the transition function with a rational re...
详细信息
ISBN:
(纸本)9783642358432
We define two-dimensional rational automata for pictures as an extension of classical finite automata for strings. they are obtained replacing the finite relation computed by the transition function with a rational relation computed by a transducer. the model provides a uniform setting for the most important notions, techniques and results presented in the last decades for recognizable two-dimensional languages, and establishes new connections between one- and two-dimensional language theory.
We consider a problem of computing the maximal value associated to the nodes of a network in the model of unknown symmetric radio network with availability of collision detection. We assume that the nodes have no init...
详细信息
ISBN:
(纸本)9783540695066
We consider a problem of computing the maximal value associated to the nodes of a network in the model of unknown symmetric radio network with availability of collision detection. We assume that the nodes have no initial knowledge about the network topology, number of nodes and even they have no identifiers. the network contains one distinguished node, called initiator, that starts the process of computing. We design a series of algorithms that result into an asymptotically optimal deterministic algorithm completing the task in theta(ecc + log Max) rounds, where ecc is the eccentricity of the initiator and Max is the maximal value among the integer values associated to the nodes. Some other utilisations of the developed algorithm are presented as well.
Many recent applications of interest involve self-interested participants. As such participants, termed agents, may manipulate the algorithm for their own benefit, a new challenge emerges: the design of algorithms and...
详细信息
ISBN:
(纸本)3540413480
Many recent applications of interest involve self-interested participants. As such participants, termed agents, may manipulate the algorithm for their own benefit, a new challenge emerges: the design of algorithms and protocols that perform well when the agents behave according to their own self-interest. this led several researchers to consider computational models that are based on a sub-field of game-theory and micro-economics called mechanism design. this paper introduces this topic mainly through examples. It demonstrates that in many cases selfishness can be satisfactorily overcome, surveys some of the recent trends in this area and presents new challenging problems. the paper is mostly based on classic results from mechanism design as well as on recent work by the author and others.
computer game-playing is a challenging topic in artificial intelligence. the recent results by the computer programs DEEP BLUE (1996, 1997) and DEEP JUNIOR (2002) against Kasparov show the power of current game-tree s...
详细信息
ISBN:
(纸本)3540207791
computer game-playing is a challenging topic in artificial intelligence. the recent results by the computer programs DEEP BLUE (1996, 1997) and DEEP JUNIOR (2002) against Kasparov show the power of current game-tree search algorithms in Chess. this success is owed to the fruitful combination of the theoretical development of algorithms and their practical application. As an example of the theoretical development we discuss a game-tree algorithm called Opponent-Model search. In contrast to most current algorithms, this algorithm uses an opponent model to predict the opponent's moves and uses these predictions to lure the opponent into uncomfortable positions. We concentrate on the time complexity of two different implementations of the algorithm and show how these are derived. Moreover, we discuss some possible dangers when applying Opponent-Model search in practice.
We present a characterization of the class of context-free trace languages in terms of cooperating distributed systems (CD-systems) of stateless deterministic restarting automata with window size 1 that are governed b...
详细信息
ISBN:
(纸本)9783642183805
We present a characterization of the class of context-free trace languages in terms of cooperating distributed systems (CD-systems) of stateless deterministic restarting automata with window size 1 that are governed by an external pushdown store.
current real-time application systems demand complex functionality and are increasingly coming to be implemented upon multiprocessor platforms, with complex synchronization, data-sharing and parallelism requirements. ...
详细信息
ISBN:
(纸本)9781424449231
current real-time application systems demand complex functionality and are increasingly coming to be implemented upon multiprocessor platforms, with complex synchronization, data-sharing and parallelism requirements. However, the formal models for representing real-time workloads have traditionally been designed in the context of uniprocessor environments;hence, they are often not able to accurately represent relevant features of multiprocessor real-time systems. Researchers have recently addressed this shortcoming by applying workload models from Divisible Load theory (DLT) to real-time systems. the resulting theory, referred to as Real-time Divisible Load theory (RT-DLT), holds great promise for modeling an emergent class of massively parallel real-time workloads. However, the theory needs strong formal foundations before it can be widely used for the design and analysis of real-time systems. In this paper, we briefly describe our current findings on RT-DLT and ongoing research efforts at extending this work to develop such formal foundations.
暂无评论