5352244
Minimal Cover-Automata for Finite Languages
A cover-automaton A of a finite language L ⊆ Σ * is a finite automaton that accepts all words in L and possibly other words that are longer than any word in L. A minimal deterministic cover automaton of a finite language L usually has a smaller size than a minimal DFA that accept L. Thus, cover automata can be used to reduce the size of the representations of finite languages in practice. In this paper, we describe an efficient algorithm that, for a given DFA accepting a finite language, constructs a minimal deterministic finite cover- automaton of the language. We also give algorithms for the boolean operations on deterministic cover automata, i.e., on the finite languages they represent.
16103350
State Complexity of Regular Languages
State complexity is a descriptive complexity measure for regular languages. We investigate the problems related to the state complexity of regular languages and their operations. In particular, we compare the state complexity results on regular languages with those on nite languages.
28358466
On Synchronization in P Systems
The P systems were recently introduced as distributed parallel computing models of a biochemical type. Multisets of objects are placed in a hierarchical structure of membranes and they evolve according to given rules, which are applied in a synchronous manner: at each step, all objects which can evolve, from all membranes, must evolve. We consider here the case when this restriction is removed. As expected, unsynchronized systems (even using catalysts) are weaker than the synchronized ones, providing that no priority relation among rules is considered. The power of P systems is not diminished when a priority is used and, moreover, the catalysts can change their states, among two possible states for each catalyst.
7865019
Follow automata
We give two new algorithms for constructing small nondeterministic finite automata (NFA) from regular expressions. The first constructs NFAs with e-transitions (eNFA) which are smaller than all the other eNFAs obtained by similar constructions. Their size is at most 3/2 |α| + 5/2, where α is the regular expression. This is very close to optimal since we prove also the lower bound 4/3; |α| + 5/2. The second constructs NFAs. It uses e-elimination in the eNFAs we just introduced and builds a quotient of the well-known position automaton w.r.t. the equivalence given by the follow relation; therefore giving the name of follow automaton. The new automaton uses optimally the information from the positions of a regular expression. We compare the follow automaton with the best constructions to date and show that it has important advantages over those.
26444044
Efficient Implementation of Regular Languages Using Reversed Alternating Finite Automata
Alternating finite automata (AFA) provide a natural and succinct way to denote regular languages. We introduce a bit-wise representation of reversed AFA (r-AFA) transition functions and describe an efficient implementation method for r-AFA and their operations using this representation. Experiments have shown that this implementation is much more efficient than, for instance, the Grail DFA implementation in both space and time.
2320487
On Synchronization Languages
New constructs for synchronization termed synchronization expressions (SEs) have been developed as high-level language constructs for parallel programming languages [8, 9]. Statements that are constrained by certain synchronization requirements are tagged, and synchronization requests are specified as expressions of statement tags. In this paper, we introduce a new family of languages named synchronization languages which we use to give a precise semantic description for SEs. Under this description, relations such as equivalence and inclusion between SEs can be easily understood and tested. In practice, it also provides us with a systematic way for the implementation as well as the simplification of SEs in parallel programming languages. We show that each synchronization language is closed under the following rewriting rules: (1) asbs → bsas, (2) atbt → btat, (3) asbt → btas, (4) atasbtbs → btbsatas and also h(atasbtbs) → h(btbsatas) for any morphism h that satisfies certain conditions which will be specified in the paper. We conjecture that closure under the above rewriting rules is a sufficient condition for a regular st-language to be a synchronization language. Several other properties of synchronization languages are also studied.
9400780
Bayesian image classification using Markov random fields
In this paper, we present three optimisation techniques, Deterministic Pseudo-Annealing (DPA), Game Strategy Approach (GSA), and Modified Metropolis Dynamics (MMD), in order to carry out image classification using a Markov random field model. For the first approach (DPA), the a posteriori probability of a tentative labelling is generalised to a continuous labelling. The merit function thus defined has the same maxima under constraints yielding probability vectors. Changing these constraints convexifies the merit function. The algorithm solves this unambiguous maximisation problem, and then tracks down the solution while the original constraints are restored yielding a good, even if suboptimal, solution to the original labelling assignment problem. In the second method (GSA), the maximisation problem of the a posteriori probability of the labelling is solved by an optimisation algorithm based on game theory. A non-cooperative n-person game with pure strategies is designed such that the set of Nash equilibrium points of the game is identical to the set of local maxima of the a posteriori probability of the labelling. The algorithm converges to a Nash equilibrium. The third method (MMD) is a modified version of the Metropolis algorithm: at each iteration the new state is chosen randomly, but the decision to accept it is purely deterministic. This is also a suboptimal technique but it is much faster than stochastic relaxation. These three methods have been implemented on a Connection Machine CM2. Experimental results are compared to those obtained by the Metropolis algorithm, the Gibbs sampler and ICM (Iterated Conditional Mode).
11243052
Improving pseudo-relevance feedback in web information retrieval using web page segmentation
In contrast to traditional document retrieval, a web page as a whole is not a good information unit to search because it often contains multiple topics and a lot of irrelevant information from navigation, decoration, and interaction part of the page. In this paper, we propose a VIsion-based Page Segmentation (VIPS) algorithm to detect the semantic content structure in a web page. Compared with simple DOM based segmentation method, our page segmentation scheme utilizes useful visual cues to obtain a better partition of a page at the semantic level. By using our VIPS algorithm to assist the selection of query expansion terms in pseudo-relevance feedback in web information retrieval, we achieve 27% performance improvement on Web Track dataset.
122735646
Segmentation using multiscale cues
Edges at multiple scales provide complementary grouping cues for image segmentation. These cues are reliable within different ranges. The larger the scale of an edge, the longer range the grouping cues it designates, and the greater impact it has on the final segmentation. A good segmentation respects grouping cues at each scale. These intuitions are formulated in a graph-theoretic framework where multiscale edges define pairwise pixel affinity at multiple grids, each captured in one graph. A novel criterion called average cuts of normalized affinity is proposed to evaluate a simultaneous segmentation through all these graphs. Its near-global optima can be solved efficiently. With a sparse yet complete characterization of pairwise pixel affinity, this graph-cuts approach leads to a hierarchy of coarse to fine segmentations that naturally take care of textured regions and weak contours.
14165952
Efficient Night Gait Recognition Based on Template Matching
Gait is a useful biometric which can be used to recognize people at a distance when other biometrics are incapable. However, most work on gait recognition has been visible spectrum-oriented over the past decade, ignoring recognition at night which is in reality demand-imperative. This paper deals with the problem of night gait recognition via thermal infrared imagery. First of all, human detection is accomplished, based on the Gaussian mixture modeling of the background. Then, human silhouettes are extracted on the basis of preceding detection results. Moreover, a new gait representation called HTI is proposed to characterize gait signatures for recognition. An infrared night gait database was built to provide a foundation for night gait recognition. Experimental results on two gait datasets show the effectiveness of this method
14436503
Implementing a Model Checker for LEGO
Interactive theorem proving provides a general approach to modelling and verification of both hardware and software systems but requires significant human efforts to deal with many tedious proofs. To be effectively used in practice, we need some automatic tools such as model checkers to deal with those tedious proofs. In this paper, we formalise a verification system of both CCS and an imperative language in the proof development system LEGO which can be used to verify both finite and infinite problems. Then a model checker, LegoMC, is implemented to generate LEGO proof terms for finite-state problems automatically. Therefore people can use LEGO to verify a general problem with some of its finite sub-problems verified by LegoMC. On the other hand, this integration extends the power of model checking to verify more complicated and infinite models as well.