This paper presents an evolution strategy used to infer fuzzy finite-state automata from examples of a fuzzy language. We describe the fitness function of an generated automata with respect to a set of examples of a f...
详细信息
ISBN:
(纸本)0780390172
This paper presents an evolution strategy used to infer fuzzy finite-state automata from examples of a fuzzy language. We describe the fitness function of an generated automata with respect to a set of examples of a fuzzy language, the representation of the transition of the automata as well as the output of the states in the evolution strategy and the simple mutation operators that work on these representations. Results are reported on the inference of a fuzzy language.
Binary unlabeled ordered trees (further called binary trees) were studied at least since Euler, who enumerated them, The number of such trees with n nodes is now known as the Catalan number. Over the years various int...
详细信息
ISBN:
(纸本)0898715962
Binary unlabeled ordered trees (further called binary trees) were studied at least since Euler, who enumerated them, The number of such trees with n nodes is now known as the Catalan number. Over the years various interesting questions about the statistics of such trees were investigated (e.g., height and path length distributions for a randomly selected tree). Binary trees find an abundance of applications in computerscience. However, recently Seroussi posed a new and interesting problem motivated by information theory considerations: how many binary trees of a given path length (sum of depths) are there? This question arose in the study of universal types of sequences. Seroussi declares that two sequences of length p have the same universal type if they generate the same set of phrases in the incremental parsing of the LempelZiv'78 scheme. (He then proves that sequences of the same type converge to the same empirical distribution.) It turns out that the number of distinct types of sequences of length p corresponds to the number of binary (unlabeled and ordered) trees, Tp, of given path length p (and also the number of different Lempel-Ziv'78 parsings of length p sequences). We first show that the number of binary trees with given path length p is asymptotically equal to Tp ∼ 22p/(log2p). Then we establish various limiting distributions for the number of nodes (number of phrases in the Lempel-Ziv'78 scheme) when a tree is selected randomly among all Tp trees. Throughout, we use methods of analytic algorithmics such as generating functions and complex asymptotics, as well as methods of appliedmath.matics such as the WKB method and matched asymptotics.
The problem of finding a piecewise straight-line path, with a constant number of line segments, in a two-dimensional domain is studied in the Turing machine-based computational model and in the discrete complexity the...
详细信息
Chemical reactions are described by edge relabeling graph transformation rules, in which a substrate chemical graph is transformed into a product chemical graph by breaking existing bonds and creating new bonds betwee...
详细信息
XP/Agile education and training remains a challenge from the perspective of determining relevant content;identifying effective methods for delivery;and maintaining the focus and motivation of students. This panel brin...
详细信息
We introduce classes of graphs with bounded expansion as a generalization of both proper minor closed classes and degree bounded classes. Such classes are based on a new invariant, the greatest reduced average density...
详细信息
One of the fundamental problems in distributed computing is how to efficiently perform routing in a faulty network in which each link fails with some probability. This paper investigates how big the failure probabilit...
详细信息
ISBN:
(纸本)9781581139945
One of the fundamental problems in distributed computing is how to efficiently perform routing in a faulty network in which each link fails with some probability. This paper investigates how big the failure probability can be, before the capability to efficiently find a path in the network is lost. Our main results show tight upper and lower bounds for the failure probability which permits routing, both for the hypercube and for the d-dimensional mesh. We use tools from percolation theory to show that in the d-dimensional mesh, once a giant component appears - efficient routing is possible. A different behavior is observed when the hypercube is considered. In the hypercube there is a range of failure probabilities in which short paths exist with high probability, yet finding them must involve querying essentially the entire network. Thus the routing complexity of the hypercube shows an asymptotic phase transition. The critical probability with respect to routing complexity lies in a different location then that of the critical probability with respect to connectivity. Finally we show that an oracle access to links (as opposed to local routing) may reduce significantly the complexity of the routing problem. We demonstrate this fact by providing tight upper and lower bounds for the complexity of routing in the random graph Gn,p. Copyright 2005 ACM.
The Object Constraint Language (OCL) is the established language for the specification of properties of objects and object structures in UML models. One reason that it is not yet widely adopted in industry is the lack...
详细信息
A common technique for modeling complex systems in many computational engineering domains is the finite element method. Analyzing these systems using the finite element method involves the application of time consumin...
详细信息
We introduce a behavior-based similarity measure which tells us whether two different space-time intensity patterns of two different video segments could have resulted from a similar underlying motion field. This is d...
详细信息
We introduce a behavior-based similarity measure which tells us whether two different space-time intensity patterns of two different video segments could have resulted from a similar underlying motion field. This is done directly from the intensity information, without explicitly computing the underlying motions. Such a measure allows us to detect similarity between video segments of differently dressed people performing the same type of activity. It requires no foreground/background segmentation, no prior learning of activities, and no motion estimation or tracking. Using this behavior-based similarity measure, we extend the notion of 2-dimensional image correlation into the 3-dimensional space-time volume, thus allowing to correlate dynamic behaviors and actions. Small space-time video segments (small video clips) are "correlated" against entire video sequences in all three dimensions (x,y, and t). Peak correlation values correspond to video locations with similar dynamic behaviors. Our approach can detect very complex behaviors in video sequences (e.g., ballet movements, pool dives, running water), even when multiple complex activities occur simultaneously within the field-of-view of the camera.
暂无评论