Research Reports 2006

HKUST-TCSC-2006-01
Yo-Sub Han and Derick Wood
Obtaining Shorter Regular Expressions from Finite-State Automata

We consider the use of state elimination to construct shorter regular expressions from finite-state automata (FAs). Although state elimination is an intuitive method for computing regular expressions from FAs, the resulting regular expressions are often very long and complicated. We examine the minimization of FAs to obtain shorter expressions first. Then, we introduce vertical chopping based on bridge states and horizontal chopping based on the structural properties of given FAs. We prove that we should not eliminate bridge states until we eliminate all non-bridge states to obtain shorter regular expressions. In addition, we suggest heuristics for state elimination that lead to shorter regular expressions based on vertical chopping and horizontal chopping.

HKUST-TCSC-2006-02
Yo-Sub Han and Kai Salomaa and Derick Wood
State Complexity of Prefix-Free Regular Languages

We investigate the state complexities of basic operations for prefix-free regular languages. The state complexity of an operation for regular languages is the number of states that are necessary and sufficient in the worst-case for the minimal deterministic finite-state automaton (DFA) that accepts the language obtained from the operation. We know that a regular language is prefix-free if and only if its minimal DFA has only one final state and the final state has no out-transitions whose target state is not a sink state. Based on this observation, we reduce the state complexities for prefix-free regular languages compared with the state complexities for (general) regular languages. For both catenation and Kleene star operations of (general) regular languages, the state complexities are exponential in the size of given minimal DFAs. On the other hand, if both regular languages are prefix-free, then the state complexities are at most linear. We also demonstrate that we can reduce the state complexities of intersection and union operations based on the structural properties of prefix-free minimal DFAs.

HKUST-TCSC-2006-03
Siu-Wing Cheng and Tamal K. Dey and Edgar A. Ramos and Raphael Wenger
Anisotropic Surface Meshing (Extended Abstract)

We study the problem of triangulating a smooth closed implicit surface Sigma endowed with a 2D metric tensor that varies over Sigma. This is commonly known as the anisotropic surface meshing problem. The 2D metric tensor can be extended naturally to a 3D metric tensor. This allows us to employ the 3D anisotropic Voronoi diagram of a set P of samples on Sigma to triangulate Sigma. It is known that the dual of a 3D anisotropic Voronoi diagram may not be a valid tetrahedralization. However, we show that a restricted dual, MeshP, is a valid triangulation and it is homeomorphic to Sigma under appropriate conditions. We also develop an algorithm for constructing P and MeshP. In addition to being homeomorphic to Sigma, each triangle in MeshP is well-shaped when measured using the 3D metric tensors of its vertices. Moreover, users can set upper bounds on the anisotropic edge lengths and the angles between the surface normals at vertices and the normals of incident triangles (measured both isotropically and anisotropically).


Web page maintained by Siu-Wing Cheng