3,854 Result(s)
within
English
Computer Science
**u Tao
Chapter
-
Chapter and Conference Paper
On the computing power of one-way cellular arrays
There are two simple models of parallel language recognizer: one-way cellular array (OCA) and one-way iterative array (OIA). For inputs of length n, both arrays consist of n identical finite-state machines (ce...
-
Chapter and Conference Paper
Signal Processing of Ultrasonic Backscattered Echoes for Evaluating the Microstructure of Materials — a Review
The microstructure evaluation of materials using ultrasonic backscattered echoes has significant practical implications. Ultrasonic backscattered grain echoes are random signals which bear information related ...
-
Chapter and Conference Paper
The High Precision DDA for Ellipse-Generatiom
In the field of computer graphics and CAD/CAM ellipses are the most fundamental curves besides circles and circular arcs. There are several kinds of algorithms for drawing ellipses now [1,2,3,4,5]. But most of...
-
Chapter and Conference Paper
Invertibility of linear finite automata over a ring
This paper deals with the invertibility problem of linear finite automata over a finite commutative ring with 1. It is shown that for any linear finite automaton M over a finite commutative ring with 1 the fol...
-
Chapter and Conference Paper
Parallel parsing on a one-way linear array of finite-state machines
Efficient parallel algorithms for some parsing problems are presented. These problems include the parsing of linear context-free languages, languages accepted by nondeterministic one-counter automata, and tran...
-
Chapter
Expert Systems for Engineering Diagnosis: Styles, Requirements for Tools, and Adaptability
Diagnosis seems a natural area for the application of expert systems. A diagnostic problem is often considered a challenge to engineers. They must exercise their intelligence to solve such a complicated puzzle...
-
Chapter and Conference Paper
Design and Display of an Analytical Surface Composed of Super- and Para-Ellipses
In this paper the authors present a theory to construct an analytical surface composed of super- and/or para-ellipses blended with other splines. This new type of surface quite fits the needs of the preliminar...
-
Chapter and Conference Paper
On the complexity of (off-line) 1-tape ATM's running in constant reversals
Yamamoto and Noguchi [YN87] raised the question of whether every recursively enumberable set can be accepted by a 1-tape or off-line 1-tape alternating Turing machine (ATM) whose (work)tape head makes only a c...
-
Chapter and Conference Paper
Some results concerning 2-D on-line tessellation acceptors and 2-D alternating finite automata
A two-dimensional nondeterministic on-line tessellation acceptor (2-NOTA) is a special type of real-time two-dimensional nondeterministic cellular automaton in which data flows from the upper-left corner to th...
-
Chapter and Conference Paper
A High Precision Digital Differential Analyzer for Circle Generation
In most applications of computer graphics, circles and circular arcs are frequently displayed. It is possible to contruct a DDA that draws a true circle; however, the logic needed for multiplications and trigo...
-
Chapter and Conference Paper
Minimal NFA problems are hard
We study the complexity of the problem of converting a deterministic finite automaton (DFA) to a minimum equivalent nondeterministic finite automaton (NFA). More generally, let A → B denote the problem of conv...
-
Chapter and Conference Paper
The structure and complexity of minimal NFA's over a unary alphabet
Many difficult open problems in theoretical computer science center around nondeterminism. We study the fundamental problem of converting a given deterministic finite automaton (DFA) to a minimal nondeterminis...
-
Chapter and Conference Paper
Static scheduling of parallel programs for message passing architectures
We discuss the static scheduling and code generation problem for message passing architectures. Using ideas from successful manually written programs for message passing architectures we have developed several...
-
Chapter and Conference Paper
Inclusion is undecidable for pattern languages
The inclusion problem for (nonerasing) pattern languages was raised by Angluin [1] in 1980. It has been open ever since. In this paper, we settle this open problem and show that inclusion is undecidable for (b...
-
Chapter and Conference Paper
On the equivalence of two-way pushdown automata and counter machines over bounded languages
It is known that two-way pushdown automata ate more powerful than two-way counter machines. The result is also true for the case when the pushdown store and counter are reversal-bounded. In contrast, we show t...
-
Chapter and Conference Paper
New decidability results concerning two-way counter machines and applications
We look at some decision questions concerning two-way counter machines and obtain the strongest decidable results to date concerning these machines. In particular, we show that the emptiness, containment, and ...
-
Chapter
Scheduling Program Task Graphs on MIMD Architectures
Scheduling is a map** of parallel tasks onto a set of physical processors and a determination of the starting time of each task. In this paper, we discuss several static scheduling techniques used for distri...
-
Chapter and Conference Paper
Approximating shortest superstrings with constraints
Various versions of the shortest common superstring problem play important roles in data compression and DNA sequencing. Only recently, the open problem of how to approximate a shortest superstring given a set...
-
Chapter and Conference Paper
On the approximation of shortest common supersequences and longest common subsequences
Finding shortest common supersequences (SCS) and longest common subsequences (LCS) for a given set of sequences are two well-known NP-hard problems. They have important applications in many areas including com...
-
Chapter and Conference Paper
Alignment of trees — An alternative to tree edit
In this paper, we propose the alignment of trees as a measure of the similarity between two labeled trees. Both ordered and unordered trees are considered. An algorithm is designed for ordered trees. The time com...
