A theory of one-tape linear-time Turing machines is quite different from its polynomial-time counterpart. this paper discusses the computational complexity of one-tape Turing machines of various machine types (determi...
详细信息
Lattice reduction algorithms have surprisingly many applications in mathematics and computerscience, notably in cryptology. On the one hand, lattice reduction algorithms are widely used in public-key cryptanalysis, f...
详细信息
ISBN:
(纸本)9783642204647
Lattice reduction algorithms have surprisingly many applications in mathematics and computerscience, notably in cryptology. On the one hand, lattice reduction algorithms are widely used in public-key cryptanalysis, for instance to attack special settings of RSA and DSA/ECDSA. On the other hand, there are more and more cryptographic schemes whose security require that certain lattice problems are hard. In this talk, we survey lattice reduction algorithms, present their performances, and discuss the differences between theory and practice.
Recent modeling experiments conducted in computational music give evidence that a number of concepts, methods and tools belonging to inverse semigroup theory can be attuned towards the concrete modeling of time-sensit...
详细信息
ISBN:
(纸本)9783319042978;9783319042985
Recent modeling experiments conducted in computational music give evidence that a number of concepts, methods and tools belonging to inverse semigroup theory can be attuned towards the concrete modeling of time-sensitive interactive systems. Further theoretical developments show that some related notions of higher-dimensional strings can be used as a unifying theme across word or tree automata theory. In this invited paper, we will provide a guided tour of this emerging theory both as an abstract theory and with a view to concrete applications.
Clock synchronization is one of the most basic building blocks for many applications in computerscience and engineering. the purpose of clock synchronization is to provide the constituent parts of a distributed syste...
详细信息
ISBN:
(纸本)9783642112652
Clock synchronization is one of the most basic building blocks for many applications in computerscience and engineering. the purpose of clock synchronization is to provide the constituent parts of a distributed system with a common notion of time. While the problem of synchronizing clocks in distributed systems has already received considerable attention from researchers and practitioners alike, we believe that there are many fascinating problems that remain unsolved. In this paper, we give a brief overview of previous work in this area;followed by a discussion of open clock synchronization problems in theory and practice.
Web science studies the interpay between web technology and the human behaviour it induces at the micro, meso and macro level. In this extended abstract we examine Web science research issues by taking a closer look a...
详细信息
ISBN:
(纸本)9783642112652
Web science studies the interpay between web technology and the human behaviour it induces at the micro, meso and macro level. In this extended abstract we examine Web science research issues by taking a closer look at the area of digital heritage. We discuss engineering, communication and socio-economic aspects.
In this paper we propose a calculus for expressing algorithms for programming languages transformations. We present the type system and operational semantics of the calculus, and we prove that it is type sound. We hav...
详细信息
ISBN:
(纸本)9783030389192;9783030389185
In this paper we propose a calculus for expressing algorithms for programming languages transformations. We present the type system and operational semantics of the calculus, and we prove that it is type sound. We have implemented our calculus, and we demonstrate its applicability with common examples in programming languages. As our calculus manipulates inference systems, our work can, in principle, be applied to logical systems.
We consider infinite two-player games played on finite graphs where the winning condition (say for the first player) is given by a regular omega-language. We address issues of optimization in the construction of winni...
详细信息
ISBN:
(数字)9783540775669
ISBN:
(纸本)9783540775652
We consider infinite two-player games played on finite graphs where the winning condition (say for the first player) is given by a regular omega-language. We address issues of optimization in the construction of winning strategies in such games. Two criteria for optimization are discussed: memory size of finite automata that execute winning strategies, and - for games with liveness requests as winning conditions - "waiting times" for the satisfaction of requests. (For the first aspect we report on work of Holtmann and Loding, for the second on work of Horn., Wallmeier, and the author.)
Probabilistic omega-automata are variants of nondeterministic automata for infinite words where all choices are resolved by probabilistic distributions. Acceptance of an infinite input word requires that the probabili...
详细信息
ISBN:
(纸本)9783540958901
Probabilistic omega-automata are variants of nondeterministic automata for infinite words where all choices are resolved by probabilistic distributions. Acceptance of an infinite input word requires that the probability for the accepting runs is positive. In this paper, we provide a summary of the fundamental properties of probabilistic omega-automata concerning expressiveness, efficiency, compositionality and decision problems.
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.
暂无评论