1007735
Structurally Unambiguous Finite Automata
We define a structurally unambiguous finite automaton (SUFA) to be a nondeterministic finite automaton (NFA) with one starting state q0 such that for all input strings w and for any state q, there is at most one path from q0 to q that consumes w. The definition of SUFA differs from the usual definition of an unambiguous finite automaton (UFA) in that the new definition is defined in terms of the transition logic of the finite automaton, and is independent of the choice of final states. We show that SUFA can be exponentially more succinct in the number of states than UFA and MDFA (deterministic finite automata with multiple initial states). Some interesting examples of SUFA are given. We argue that SUFA is a meaningful concept, and can have practical importance as it can implemented efficiently on synchronous models of parallel computation.
683638
Descriptional Complexity of Machines with Limited Resources
Over the last 30 years or so many results have appeared on the descriptional complexity of machines with limited resources. Since these results have appeared in a variety of different contexts, our goal here is to provide a survey of these results. Partic- ular emphasis is put on limiting resources (e.g., nondeterminism, ambiguity, lookahead, etc.) for various types of finite state machines, pushdown automata, parsers and cellu- lar automata and on the effect it has on their descriptional complexity. We also address the question of how descriptional complexity might help in the future to solve practical issues, such as software reliability.
15682339
Measuring nondeterminism in pushdown automata
The amount of nondeterminism that a pushdown automaton requires to recognize an input string can be measured by the minimum number of guesses that it must make to accept the string, where guesses are measured in bits of information. When this quantity is unbounded, the rate at which it grows as the length of the string increases serves as a measure of the pushdown automaton's ''rate of consumption'' of nondeterminism. We show that this measure is similar to other complexity measures in that it gives rise to an infinite hierarchy of complexity classes of context-free languages differing in the amount of the resource (in this case, nondeterminism) that they require. In addition, we show that there are context-free languages that can only be recognized by a pushdown automaton whose nondeterminism grows linearly, resolving an open problem in the literature. In particular, the set of palindromes is such a language.
42246755
A Constraint-Based Interactive Train Rescheduling Tool
In this paper, we formulate train rescheduling as constraint satisfaction problem and describe a constraint propagation approach to tackle it. Algorithms for timetable verifications and train rescheduling are designed under a coherent framework. We define two optimality criteria that correspond to minimizing passenger delay and the number of station visit modifications respectively for rescheduling. Two heuristics are then proposed to speed up and direct the search towards the optimal solutions. The feasibility of our proposed algorithms and heuristics are confirmed with experimentation using real-life data.
8282971
Protein Subcellular Localization Based on Psi-blast and Machine Learning
Subcellular location is an important functional annotation of proteins. An automatic, reliable and efficient prediction system for protein subcellular localization is necessary for large-scale genome analysis. This paper describes a protein subcellular localization method which extracts features from protein profiles rather than from amino acid sequences. The protein profile represents a protein family, discards part of the sequence information that is not conserved throughout the family and therefore is more sensitive than the amino acid sequence. The amino acid compositions of whole profile and the N-terminus of the profile are extracted, respectively, to train and test the probabilistic neural network classifiers. On two benchmark datasets, the overall accuracies of the proposed method reach 89.1% and 68.9%, respectively. The prediction results show that the proposed method perform better than those methods based on amino acid sequences. The prediction results of the proposed method are also compared with Subloc on two redundance-reduced datasets.
206606372
A Web-Based Chinese Handwriting Education System with Automatic Feedback and Analysis
We propose a web-based Chinese handwriting system that allows students to learn Chinese handwriting at anytime and anywhere. The system combines technologies such as electronic ink, database, Flash animations, and pattern recognition technique to provide students with an intelligent and effective learning environment. In particular, our system contains an Automatic Feedback and Analysis (AFA) tool that can check multiple kinds of handwriting mistakes and provide useful feedback to the user. Survey results show that most users agreed that our proposed system can help them to learn Chinese handwriting more efficiently as well as reducing teachers’ workload. The user evaluation results suggest that it takes less time for users to learn Chinese handwriting with our system than with traditional teaching method.
33568725
A novel M-ary chaotic spread spectrum communication scheme for DSRC system in ITS
In this paper, a novel non-coherent M-ary chaotic spread spectrum communication scheme is proposed for dedicated short range communications (DSRC) in intelligent transportation systems (ITS). The proposed scheme encodes the M-ary information symbols on to the bifurcation parameter of a chaotic system. This new chaotic communication scheme exploits the ergodic properties of chaotic signals for demodulating the received signal. The proposed scheme is basically non-coherent which eliminates the complex synchronization procedure. Furthermore, the proposed scheme utilizes a low complexity multipath mitigation technique to combat fading. Performance analysis shows the superior communication performance of the proposed chaotic spread spectrum scheme over conventional spread spectrum schemes in rapid multipath fading environments. Thus, the developed scheme is attractive in terms of communication performance, multipath mitigation, and system complexity.
18767073
Fitting Ellipses to a Region with Application in Calligraphic Stroke Reconstruction
Given a region, it is a challenge to find a set of primitive shapes such as rectangles, circles or ellipses to cover it. This is in fact a set-covering problem, which is known to be NP-hard. The focus of this paper is on fitting a set of ellipses onto an image region. This problem was first formulated by identifying a number of criteria required for the ellipse fitting. A solution is then proposed for automatically determining the set of ellipses that best fits onto an image region. The proposed ellipse fitting algorithm has also been applied to strokes forming characters of Chinese calligraphic artwork. The results show that our proposed algorithm generates ellipses fitting onto stroke regions and capturing the characteristics of the strokes during turning, tilting and back-trace.