|
PAVAN
ADURI, Assistant Professor
of Computer Science
Ph.D. 2001, Computer Science, University
at Buffalo, Buffalo
Major Interests:
Computational Complexity: Average-case
complexity, Connections between average-case complexity
and worst-case complexity, Properties of complete
languages.
Current Research:
A major goal of Dr. Aduri's research
is to understand the structure and complexity of the
class NP. Dr. Aduri's current research is focused
on the following themes:
- Relations between average-case
complexity and worst-case complexity: Some problems
such as Permanent have the fascinating property
that if they are easy on average, then they are
easy in worst-case. Thus, the worst-case hardness
of Permanent is the same as its average-case hardness.
Can we show similar results for problems in NP,
say Satisfiability or Hamiltonian Cycle?
- Properties of NP-complete sets:
What makes a set complete? Can we identify the properties
responsible for completeness? How hard/easy are
complete sets? How much information/redundancy is
their in complete sets?
Representative Publications:
Hitchcock, J. and Pavan, A. (2006).
Comparing reductions to complete sets. 33rd International
Colloquium on Automata, Languages and Programming,
LNCS 4051:465-476.
Glasser, C., Pavan, A., Selman, A.
and Zhang, L. (2006). Redundancy in complete sets.
23rd International Symposium on Theoretical Aspects
of Computer Science, LNCS 3884:444-454.
Glasser, C., Pavan, A., Selman, A.,and
Sengupta, S. (2007). Properties of NP-complete sets.
SIAM Journal on Computing, In press.
Hitchcock, J., Pavan, A., Vinodchandran,
N. V. (2004). Partial bi-immunity and NP-completeness.
Proceedings of the 19th IEEE Conference on Computational
Complexity, 198-203.
SAMIK
BASU, Assistant Professor of Computer Science
Ph.D. 2003, Computer Science, State
University of New York at Stony Brook
Major Interests:
Formal methods, specification and
verification of systems, model checking.
Current Research:
The main thrust of Dr. Basu's research
is to develop techniques for the verification of infinite-state
systems (protocols, embedded systems, source-code)
and to ensure the safety and reliability of software
systems. Two major activities of his research include
(a) developing efficient techniques to detect system
flaws and (b) enhancing debugging capabilities by
building effective justification of the cause of these
flaws. Dr. Basu is also involved in projects on supervisory
control, protocol conversion, open system verification
and service composition where the primary objective
is to generate controllers or converters or choreographers
that can force the systems to behave in a desirable
fashion. In addition, Dr. Basu actively participates
in projects involving the application of formal techniques
for developing intrusion detection and response systems.
Representative Publications:
Basu, S and Ramakrishnan, C.R. (2006).
Compositional Analysis for Verification of Parameterized
Systems. Journal of Theoretical Computer Science (TCS).
Yang, P., Basu, S. and Ramakrishnan,
C.R.. Parameterized Verification of Pi-Calculus Systems.
International Conference on Tools and Algorithms for
the Construction and Analysis of Systems (TACAS).
Basu, S., Roop, P.S.and Sinha, R.
(2006) Local Module Checking for CTL specifications.
Formal Foundations of Embedded Software and Component-Based
Software Architectures (FESCA). Best Paper Award.
Basu, S. and Kumar, R. (2006) Quotient-based
Control Synthesis for Non-Deterministic Plants with
Mu-Calculus Specifications.IEEE Conference on Decision
and Control (CDC).
Kumar, R., Zhou, C., and Basu, S.
(2006) Finite Bisimulation ofReactive Untimed Infinite
State Systems Modeled as Automata with Variables.
American Control Conference (ACC).
Pathak, J., Basu, S., Lutz, R. and
Honavar, V.(2006). Selecting and Composing Web Services
through Iterative Reformulation of Functional Specifications
. Proceedings of the IEEE International Conference
on Tools with Artificial Intelligence (ICTAI 2006),
Washington, DC, IEEE. (Best Paper Award).
Pathak, J., Basu, S., and Honavar,
V.Modeling Web Services by Iterative Reformulation
of Functional and Non-Functional Requirements.4th
International Conference on Service Oriented Computing
(ICSOC 2006).
Pathak, J., Basu, S., Lutz, R. and
Honavar, V. (2006). Parallel Web Service Composition
in MoSCOE: A Choreography-based Approach.4th IEEE
European Conference on Web Services (ECOWS 2006).
Stakhanova, N., Basu, S., Lutz, R.
and Wong, J. (2006).Automated Caching of Behavioral
Patterns for Efficient Run-time Monitoring. IEEE International
Symposium on Dependable, Autonomic and Secure Computing
(DASC 2006).
YING
CAI, Assistant Professor of Computer Science
Ph.D. 2002, Computer Science, University
of Central Florida
Major Interests:
Mobile Computing and Networking,
Peer-to-Peer Systems, Multimedia Communications.
Current Research:
Dr. Cai is investigating a new type
of computing called geotasking.A geotasking system
is formed by a set of position-aware mobile hosts
that communicate with each other through wireless
networks. Geotasking treats the geographic environment
as its storage disk; as mobile hosts move, they load
and execute the programs implanted in their surroundings.The
research aims at addressing various aspects of geotasking,
including execution triggers, dynamic binding, and
concurrent execution of geotasks with memory mapping.In
addition to geotasking, Dr. Cai is developing a new-generation
peer-to-peer framework for large-scale and cost-effective
distributions of video data, either prerecorded or
live, over the Internet. The research in this area
is to investigate a suite of innovative solutions
for topology-aware video storage, streaming and downloading,
and service scheduling.
Representative Publications:
Cai, Y. and Zhou, J. (2007). An Overlay
Subscription Network for Live Internet TV Broadcast.
IEEE Transactions on Knowledge and Data Engineering.
In press.
Cai, Y., Natarajan, A., and Wong, J. (2007). On Scheduling
of Peer-to-Peer Video Services. IEEE Journal on Selected
Areas in Communications, Peer-to-Peer Communications
and Applications In press.
Cai, Y., Chen, Z., and Tavanapong, W. (2007). Caching
Collaboration and Cache Allocation in Peer-to-Peer
Video Systems . Journal of Multimedia Tools and Applications.
In press.
Cai, Y., Hua, K. A., Cao, G., and Xu, T. (2006).Real-Time
Processing of Range-Monitoring Queries in Heterogeneous
Mobile Databases.IEEE Transactions on Mobile Computing.
Vol. 5. No. 7. pp. 931-942, 2006.
Cai, Y., and Hua, K. A.Sharing Multicast
Videos Using Patching Streams. Journal of Multimedia
Tools and Applications. Vol.21, No.2, pp. 125-146,
2003.
CARL
K. CHANG, Professor and Chair of Computer Science
Ph.D. 1982, Computer Science, Northwestern
University, Evanston, Illinois
Major Interests:
Requirements Engineering, Software
Architecture, Services Computing, Collaboration Technology,
Project Management.
Current Research:
Dr. Chang's research in software
engineering includes two major activities: software
architecture based requirements engineering and project
management with genetic algorithms. His research in
net-centric computing currently focuses on rule-mitigated
collaboration technology to support formal electronic
meetings. His interests in services computing include
dynamic composition and QoS issues of web services,
requirements analysis and decomposition of service-oriented
architecture with aspects, and service pricing strategies.
Representative Publications:
Xia, J., Chang, C. K., Wise, J. and
Ge, Y. (2006). An Empirical Performance Study on PSIM.
The Computer Journal, Oxford University Press. Vol.
49. No. 5. pp. 509-526.
Zhang, J., Chang, C., Hung, P., and
Zhang, L.-J. Phased Transformation toward Services-Oriented
Architecture. Accepted by IEEE Transactions on Systems,
Man, and Cybernetics, Part A.
Kim, T. and Chang, C. (2006) An Aspect-Oriented
Approach to Resource Composition in Petri net-based
Software Architectural Models. 30th Annual International
Computer Software and Applications Conference (COMPSAC
2006), Chicago. pp. 87-94.
Xia, J., Ge, Y., and Chang, C. (2005).
An Empirical Performance Study for Validating a Performance
Analysis Approach: PSIM. Proc. of 29th Annual International
Computer Software and Applications Conference (COMPSAC
2005), July 26-28, 2005, Edinburgh, Scotland, UK,
pp. 307-312. Best Paper.
Kim, T. and Chang, C. Service-Oriented
Design with Aspects (SODA). (2005). IEEE Int'l Conf.
Services Computing (SCC 2005), Orlando, FL. pp. 319-324.
Cleland-Huang, J., Chang, C.and Christensen,
M (2003). Event-Based Traceability for Managing Evolutionary
Change. IEEE Transactions in Software Engineering.
Vol. 29. No. 9. pp. 796 - 810.
Cleland-Huang, J., Chang, C. K. and
Wise, J. (2003). Automating performance-related impact
analysis through event based traceability. Requirements
Engineering Journal, Springer-Verlag. Vol. 8. No.
3. pp. 171 - 182.
Cai, L., Chang, C., and Cleland-Huang,
J. Supporting Agent-based Distributed Software Development
through Modeling and Simulation. Prof. of 2003 IEEE
Workshop on Future Trends of Distributed Computing
Systems, San Juan, Puerto Rico. pp. 56-62, 2003.
Cleland-Huang, J., Chang, C.K., Sethi,
G., Javvaji, K., Hu, H., andXia, J. (2002). Automating
speculative queries through event-based requirements
traceability. Proceedings IEEE Joint Int'l Conf. Requirements
Engineering (RE'02), Essen, Germany. pp. 289-296.
Best Research Paper.
Chang, C., Cleland-Huang, J., Hua,
S. and Combelles, A. (2001). On Function-Class Decomposition.
IEEE Computer, Dec. 2001, pp. 87-93.
Chang, C., Zhang, T. and Christensen,
M. (2001). Genetic Algorithms for Project Management.
Annals of Software Engineering, Kluwer Academic Publishers,
11:107-139, Nov. 2001.
Chang, C. and Shih, C-C. (1999).
A Circular Skip-Cluster Scheme to Support Video-on-Demand
Services. ACM Multimedia Systems, Springer-Verlag,
7(2):107-118.
SOMA
CHAUDHURI, Associate Professor of Computer Science
Ph.D. 1990, Computer Science &
Engineering, University of Washington
Research Interests:
Theory of distributed computing:
distributed algorithms in shared memory and message
passing models of computation; distributed data structures;
algorithms, lower bounds and impossibility results
for asynchronous and partially synchronous systems;
fault-tolerance. Mobile Computing: theoretical models,
lower bounds and algorithms for computing in ad hoc
networks. Security Protocols: Distributed Consensus-based
algorithms in security. Software Obfuscation and Watermarking.
Secret Sharing, Security Policies.
Current Research:
Dr. Chaudhuri's research in the theory
of distributed computing systems includes algorithm
design and analysis, and lower bounds and impossibility
results for a variety of problems, including consensus,
set consensus and resource allocation. She is particularly
interested in studying the complexities that arise
due to the presence of uncertainty caused by asynchrony
and failures in distributed systems. Her research
focused on understanding the differences in computational
power between a variety of timing models, ranging
from synchronous to asynchronous models of distributed
computation. Dr. Chaudhuri has also done research
on consistency conditions for distributed shared memory.
The problem here is to define consistency conditions
that are weak enough that they are easy to support
by the underlying architecture but still strong enough
to allow correctness of concurrent programs. Dr. Chaudhuri
is also interested in algorithms and lower bounds
for distributed data structures.
Dr. Chaudhuri has interests in the
area of mobile, ad hoc and wireless networks. Such
networks are unpredictable due to frequent link failures
when nodes drift apart and link formations when nodes
drift closer to each other. Existing distributed algorithms
that rely on static communication links cannot run
in such networks. Instead, efficient algorithms would
have to be designed that adjust to the mobility of
the network.
Another of Dr Chaudhuri's research
interests lies in Security in Distributed Systems.
Software protection ensures the digital rights of
the software vendors. Specific technologies to support
software protection are software obfuscation, anti-tamper,
and watermarking. Obfuscation makes it hard for a
hacker to learn anything more about the program than
he needs to be able to use the program; specifically
it makes it hard to reverse-engineer the high level
program from the machine level code and observation
of its black-box behavior. There has been theoretical
work that has formalized the notion of obfuscation
and shown that there exist functions that cannot be
obfuscated. Dr. Chaudhuri is interested in developing
new definitions for obfuscation that are more useful
in practice, and come up with existence and impossibility
results.
Some distributed problems dealing
with asynchronous communication arise within the context
of large scale embedded system designs. Those issues
are also being explored.
Representative Publications:
Ge, J., Chaudhuri, S. & Tyagi,
A.(2005). "Control-Flow Based Obfuscation."
Proceedings of the Fifth ACM Workshop on Digital Rights
Management.
Chaudhuri, S.,Herlihy, M., Lynch,
N. & Tuttle, M. (2000). "Tight Bounds for
k-Set Agreement." Journal of the ACM, 47
(5): 912--943, November 2000.
Chaudhuri, S.,Kosa, M. & Welch,
J. (2000). "One-Write Algorithms for Multi-Valued
Regular and Atomic Registers," Acta Informatica,
37 (3): 61-192.
Chaudhuri, S.,Herlihy, M. & Tuttle,
M. (1999) "Wait-Free Implementations in Message
Passing Systems." Theoretical Computer
Science, 220 (1): 211-245, June 1999.
Chaudhuri, S., Attiya, H., Friedman,
R. &Welch, W. (1998). "Shared Memory Consistency
Conditions for Non-Sequential Execution: Definitions
and Programming Strategies," SIAM Journal
on Computing, 27 (1): 65-89, February 1998.
Chaudhuri, S. & Reiners, R. (1996).
"Understanding the Set Consensus Partial order
Using the Borowsky-Gafni Simulation," Proceedings
of the Tenth International Workshop on Distributed
Algorithms, 1996. Lecture notes in Computer
Science 1151, Springer-Verlag, pp. 362-379.
Chaudhuri, C., Coan, B. & Welch,
J.(1995). "Using Adaptive Timeouts to Achieve
At-Most-Once Message Delivery," Distributed
Computing, 9 (3): 109-117, September 1995.
Chaudhuri, C. & Welch, J. (1994).
"Bounds on the Costs of Multi-Valued Register
Implementations," SIAM Journal on Computing,
23 (2): 335-354, April 1994.
Chaudhuri, S., Gawlick, R. &
Lynch, N. (1993). "Designing Algorithms for Distributed
Systems with Partially Synchronized Clocks,"
Proceedings of the Twelfth Annual ACM Symposium on
Principles of Distributed Computing, August 1993.
Chaudhuri, S. (1993). "More
Choices Allow More Faults: Set Consensus Problems
in Totally Asynchronous Systems," Information
and Computation, 105 (1): 132-158, July 1993.
HUI-HSIEN
CHOU, Associate Professor of Computer Science
& Genetics, Development & Cell Biology
Ph.D., 1996, Computer Science, University
of Maryland at College Park
Major Interests:
Bioinformatics and computational
biology; cellular automata and artificial life; and
programming methods and compiling.
Current Research:
Dr. Chou's research centers around
two complementary areas: computational biology and
artificial life. In computational biology he studies
how to best analyze the vast amount of biological
data generated by high-throughput genomics and transcriptomics
studies. These studies allow us to gather explosively
more biological data, but only computers can efficiently
analyze the resulted huge quantity of data. Previously
Dr. Chou has designed DNA sequence quality assurance
and microarray design software. He is currently developing
an integrated approach of biological data analysis
that combines sequence, structure, microarray and
pathway data to better assist biologists to gain novel
biological insights. He has also created an automatic
Perl programming tool, which can automatically generates
working Perl programs for biologists who may not know
how to program in Perl directly.
Dr. Chou's work on artificial life
has focused on the use of cellular automata to model
self-replication. Dr. Chou has developed the Trend
cellular automata programming language for programming
cellular automata models.
Representative Publications:
Maher, P., Chou, H-H., Hahn, E.,
Wen, T-J. and Schnable, P. (2006). GRAMA: Genetic
mapping analysis of temperature gradient capillary
electrophoresis (TGCE) Data. Theoretical and Applied
Genetics, 113(1):156-162, June 2006.
Chou, H-H. (2005). Computational
Design of Whole Genome Microarrays. In Srinivas Aluru,
editor, Handbook of Computational Molecular Biology.
ISBN 1584884061. CRC Press, Boca Raton, FL, 2005.
Chou, H-H. (2005). Vect: an automatic
visual Perl programming tool for nonprogrammers. BioTechniques,
38:615-621, April 2005.
Li, S. and Chou, H-H. (2005). UBViz:
Explore Biochemical Pathways in 3-D Space. BioTechniques,
38:540-542, April 2005.
Chou, H-H., Hsia, A-P., Mooney, D.
and Schnable. P., (2004).Picky: Oligo Microarray Design
for Large Genomes. Bioinformatics, 20:2893-2902, Nov.
2004.
Li, S. and Chou, H-H. (2004).Lucy2:
an interactive DNA sequence quality trimming and vector
removal tool. Bioinformatics, 20:2865-2866, Nov. 2004.
Huang, X., Ye, L.,Chou, H-H., Yang,
I-H. and Chao, K-M. (2004). Efficient Combination
of Multiple Word Models for Improved Sequence Comparison.
Bioinformatics, 20:2529-2533,
Nov. 2004.
Chou, H-H., Huang, W., and Reggia,
J. (2002). The Trend Cellular Automata Programming
Environment. Simulation, 78:59−75, Feb. 2002.
Chou, H-H., and Holmes, M. (2001).
DNA Sequence Quality Trimming and Vector Removal.
Bioinformatics, 17:1093−1104, Dec. 2001.
Myers, E., Sutton, G., Delcher, A.,
Dew, I., Fasulo, D., Flanigan, M., Kravitz, S., Mobarry,
C.,Reinert, K., Remington, K., Anson, E., Bolanos,
R.,Chou, H-H., Jordan, C., Halpern, A., Lonardi,S.,
Beasley, E., Brandon, R., Chen, L., Dunn, P., Lai,
Z., Liang, Y., Nusskern, D., Zhan, M.,Zhang, Q., Zheng,
X., Rubin, G., Adams, M., and Venter, J. C. (2000).
A Whole-Genome Assembly of Drosophila. Science, 287:2196−2204,
March 24, 2000.
OLIVER
EULENSTEIN, Associate Professor of Computer Science
Ph.D. 1998, Computer Science, University
at Bonn, Germany
Major Interests:
Algorithms, Computational Complexity,
Bioinformatics and Computational Biology.
Current Research:
Dr. Eulenstein's research area is
in computational biology, that is, the development
of computational methods and algorithms for molecular
biology. In particular, his research is aimed at supporting
evolutionary biologists with powerful computational
tools in their efforts to construct the Tree of Life.
This tree connects all life on earth through a complex
tree-like structure of evolutionary relationships.
Connecting the estimated 4 trillion species (from
which only about 1.75 million are recorded), the Tree
of Life is of enormous size. However, a description
of this tree will provide biologists with a predictive
power similar to the one that chemists have from the
Periodic Table of Elements. Thus, knowing the Tree
of Life, or large parts of it, would result in an
enormous benefit to science and society. Unfortunately,
only very small parts of the Tree of Life could be
constructed so far. Evolutionary biologists are faced
with the problem assembling the Tree of Life from
the phylogenetic information of over 1.75 million
recorded species. In analogy, this task is similar
to the task of assembling a complex alien starship
from its pieces without having any documentation.
However, advances in the development of powerful algorithms
will allow evolutionary biologists to assemble large
parts of the Tree of Life within the next two decades.
As part of an interdisciplinary research team, it
is Dr. Eulenstein's research mission to meld the power
of algorithm theory with the biologists' expert-knowledge
into applications that will allow constructing large
parts of the Tree of Life.
Representative Publications:
Bansal, M., Burleigh, G., Eulenstein,
O., and Wehe, A.."Heuristics for the Gene-duplication
Problem: An Omega(n)Speed-up for the Local Search"
(accepted), RECOMB 07
Chen, D.,Burleigh, J.G., Eulenstein,
O.and Fernández-Baca, D. (2006). Improved heurisitcs
for minimum-flip supertree construction; evolutionary
bioinfor-matics. Evolutionary Bioinformatics, (accepted).
Chen, D., Eulenstein, O., Fernández-Baca,
D., and Sanderson M. J. (2006). Minimum-flip supertrees.
IEEE Transactions on Computational Biology and Bioinformatics,
3(2):165-173.
Wilkinson, M., Cotton, J. A., Creevey,
C., Eulenstein, O., Harris, S. R., Lapointe, F., Levasseur,C.,
Mcinerney, J. O., Pisani, D. and Thorley J. L. (2005).
The shape of supertrees to come: Tree shape related
properties of fourteen supertree methods. Systematic
Biology, 54(3):419-431.
Yan, C., Burleigh, J. G., and Eulenstein
O. (2005). Identifying optimal incomplete phylogenetic
data sets from sequence databases. Molecular Phylogenetics
and Evolution, 35:528-535.
Chen, D., Eulenstein, O. and Fernández-Baca,
D. (2004). Rainbow: A tool-box for phylogenetic supertree
construction and analysis. Bioinformatics,20(16):2872-2873.
Eulenstein, O.,Chen, D., Burleigh,
J. G., Fernández-Baca, D. and Sanderson M.
J. (2004). Performance of flip-supertree construction.
Systematic Biology, 53(2):1-10.
Eulenstein, O. and Vingron, M. (1998).
On the equivalence of two tree mapping measures. Discrete
Applied Mathematics, 88:103-128.
Eulenstein, O., Mirkin, B.and Vingron,
M. (1998). Duplication based measures of difference
between gene- and species trees. Journal of Computational
Biology, 5:135-148.
Chang, W. and Eulenstein, O. (2006).
Reconciling trees with apparent polytomies; computing
and combinatorics. In D. Z. Chen and D. T. Lee, editors,
2th Annual International Conference. Lecture Notes
in Computer Science, number 4112 in LNCS, pages 235-244.
Springer.
DAVID
Fernández-Baca, Professor of Computer Science
Ph.D. 1986, Computer Science, University
of California, Davis
Major Interests:
Design and analysis of algorithms,
combinatorial optimization, graph algorithms, computational
biology, computational phylogenetics, sensitivity
analysis.
Current Research:
Dr. Fernández-Baca's two main
areas of research are sensitivity analysis of optimization
problems and the construction of evolutionary (phylogenetic)
trees.The goal of the first of these fields is to
determine how the optimum solutions to optimization
problems are affected by changes in the input data.
Dr. Fernández-Baca's work has led to sensitivity
analysis algorithms for specific problems, such as
computing minimum spanning trees, as well as general-purpose
techniques that apply to a variety of problems.He
also studies how statistical models of biological
sequence comparison are affected by changes in assumptions
about evolutionary distance.
Dr. Fernández-Baca's other
area of research aims to develop efficient algorithms
for building reliable evolutionary trees for sets
of species.He has studied issues surrounding the method
of parsimony, which seeks a tree that explains evolution
using the fewest number of evolutionary changes. He
is also interested in two related problems: reconciling
conflicting phylogenetic information -the "supertree"
problem - and partitioning phylogenetic information
into highly compatible subsets - that is, into clusters
that provide similar evolutionary "signal." Additionally,
Dr. Fernández-Baca studies problems at the
boundary between phylogenetics and sensitivity analysis,
such the effect of evolutionary distance on tree construction.
Representative Publications:
D. Fernández-Baca and B. Venkatachalam.
Sensitivity Analysis in Combinatorial Optimization.
To appear in Handbook of Approximation Algorithms
and Metaheuristics (T. Gonzalez, ed.), Chapman and
Hall/CRC Press Computer and Information Science Series.
D. Chen, O.
Eulenstein, D. Fernández-Baca, and M.J.
Sanderson. Minimum flip supertrees: Complexity
and algorithms. IEEE Trans. Bioinformatics and Computational
Biology, April-June
2006 (Vol. 3, No. 2) pp. 165-173.
D. Fernández-Baca and B. Venkatachalam.
Parametric analysis for ungapped Markov models of
evolution. In Proc. Combinatorial Pattern Matching,
Springer LNCS, Vol. 3537, pp. 394-405, 2005.
D. Fernández-Baca and B. Venkatachalam.
Parametric sequence alignment. In Handbook of Computational
Molecular Biology (S. Aluru, ed.), Chapman and Hall/CRC
Press Computer and Information Science Series, 2005.
F. Sun, D. Fernández-Baca,
and W. Yu. Inverse
parametric sequence alignment. Journal of Algorithms,
53(1):36--54 (2004).
D. Chen, O.
Eulenstein, and D. Fernández-Baca. Rainbow:
A toolbox for phylogenetic supertree construction
and analysis. Bioinformatics
20(16):2872-2873 (2004).
D. Fernández-Baca, T.
Seppäläinen, and G. Slutzki. Parametric
multiple sequence alignment and phylogeny construction.
Journal of Discrete Algorithms, 2(2):271-287 (2004),
special issue on Combinatorial Pattern Matching, edited
by R. Giancarlo and D. Sankoff.
Eulenstein, O., Chen, D., Burleigh
J.G., Fernández-Baca, D.and Sanderson.
M.J. (2004). Performance
of flip supertrees with a heuristic algorithm.
Systematic Biology,
53(2):299-308, 2004.
Fernández-Baca, D.and Lagergren, J. (2003). A polynomial-time
algorithm for near-perfect phylogeny. SIAM
J. Computing, 32(5):1115-1127.
Chen D., Diao L., Eulenstein
O.,Fernández-Baca D. and Sanderson
M.J. (2003). Flipping: A supertree construction method.
In Bioconsensus, M. Janowitz et al. (eds), DIMACS
Series in Discrete Mathematics and Theoretical Computer
Science, vol. 61, pp. 135-160, American Mathematical
Society.
Fernández-Baca, D. (2003).
Decomposable
multiparameter matroidal knapsack problems. Theoretical
Computer Science, 297:183-198.
Fernández-Baca, D., Seppäläinen,
T. and Slutzki, G. (2002). Bounds for parametric sequence
comparison. Discrete Applied Mathematics, 118:181-198.
Fernández-Baca, D. (2001).
The perfect phylogeny problem. In Steiner Trees in
Industry, X. Cheng and D.-Z. Du (eds.), pp. 203-234,
Kluwer.
Fernández-Baca, D. (2001).
On nonlinear parametric search. Algorithmica, 30:1-11.
SHASHI
K. GADIA, Associate Professor of Computer Science
Ph.D. 1977, Mathematics, University
of Illinois
Major Interests:
Temporal,
spatial, belief, security, stastical and incomplete
data; database models, type hierarchy, languages,
user interfaces, optimization, implementation and
access methods; pattern matching in spatio-temporal
data.
Current Research:
Dr. Gadia's major research interests
center around storage and retrieval of parametric
data, data with underlying dimensions such as space,
time, and beliefs and XML (extendible markup language).
Dr. Gadia's research on parametric data has led to
the development of ParaSQL, a natural query language
for users of parametric data. Hisresearch on XML has
led to the development of a novel storage technology
CanStoreX.
Representative Publications:
Noh, S-Y. and Gadia, S. (2006). A
Comparison of Two Approaches to Utilizing XML in Parametric
Databases for Temporal Data. Information and Software
Technology, Vol 48, pp807-819.
Noh, S-Y. and Gadia, S. (2005) An
XML-based Framework for Temporal Database Implementation.
Proc. Twelfth International Symposium on Temporal
Representation and Reasoning.
Bertino, E., Cheng, T., Gadia, S.
and Guerrini, G. (2001). A linguistic framework for
multidimensional data, Proceedings Eighth International
Symposium on Temporal Representation and Reasoning.
Merlo, I., Bertino, E., Ferrari,
E., Gadia, S. and Guerrini, G. (2000). Querying multiple
temporal granularity data. Proceedings Seventh International
Workshop on Temporal Representation and Reasoning.
Gadia, S. and Nair, S. (1998). Algebraic
identities and query optimization in the parametric
model for relational temporal databases. IEEE Transactions
on Knowledge and Data Engineering. Vol 10(5), pp 793-807.
Gadia, S. and Bhargava, G. (1993).
Relational Database Systems With Zero Information-Loss.
IEEE Transactions on Knowledge and Data Engineering,
5:76-87.
Gadia, S., Nair, S., & Poon,
Y. (1993) "Incomplete Information in Relational
Temporal Databases,". Proceedings of the 18th
International Conference on Very Large Databases,
pp. 395-406.
Gadia, S. and Bhargava, G.The concept
of an error in a database: an application of temporal
databases. Appeared in Proceedings of INSDOC COMAD90
International Conference on Management of Data, December
1990.
Gadia, S. and Yeung, C-S. (1998).
A Generalized Model for a Relational Temporal Database.
ACM SIGMOD Conference on Management of Data, pp. 251-259.
Gadia, S. (1998). A Homogeneous Relational
Model and Query Languages for Temporal Databases.
ACM Transactions on Database Systems, 14:418-448.
VASANT
HONAVAR, Professor of Computer Science
Ph.D. 1990, Computer Science and
Cognitive Science, University of Wisconsin, Madison
Major Interests:
Artificial Intelligence, Machine
Learning, Neural Computation, Probabilistic models,
Bioinformatics, Computational Molecular and Systems
Biology, Computational Neuroscience, Data Mining,
Computational Learning Theory,Information Integration,
Ontologies, Knowledge Representation, and Inference,
Semantic Web, Service-Oriented Computing,e-Science
Infrastructure, Knowledge Discovery Applications in
Enterprise Informatics, Medical Informatics, Engineering
informatics, Materials Informatics, Security Informatics,
Environmental Informatics etc.
Current Research:
Dr. Honavar's recent research has
led to:
- The development of new sufficient
statistics based framework, and algorithms that
are provably exact relative to their centralized
counterparts, and their open source implementations
for learning classifiers from distributed dataand
multi-relational data
- The development of an ontology-driven,
federated approach to flexible integration of semantically
disparate information sources, with emphasis on efficient
answering of statistical queries from such data sources
- Development of extensions to description
logics (DL) to support modular knowledge bases, distributed
inference, selective knowledge sharing and knowledge
reuse (resulting in a family of modular ontology languages
called package-based description logics, or P-DL)
- Development of approaches specification-driven
assembly of complex services from components services
- Development of novel machine learning
algorithms for several problems motivated by real-world
learning scenarios e.g., learning classifiers from
partially specified data, multi-relational data, multi-instance
data, and alternately structured data (e.g., molecular
sequences, molecular structures, gene expression patterns)
- Application of machine learning
algorithms to problems in computational and systems
biology including protein function classification,
prediction of functionally important sites of proteins
(e.g., protein-protein, protein-DNA, and protein-RNA
interfaces, phosphorylation and glycosylation sites),
and elucidation of regulatory networks and pathways
Honavar's research is supported in
part by grants from the National Science Foundation,
the National Institutes of Health, the Department
of Energy, and the ISU Center for Computational Intelligence,
Learning, and Discovery.Much of this research has
been carried out in collaboration with current and
former graduate students. Additional information can
be found at www.cs.iastate.edu/~honavar/aigroup.html
Representative Publications:
Bao, J., Caragea, D., and Honavar,
V. (2006). On the Semantics of Linking and Importing
in Modular Ontologies. In Proceedings of the International
Semantic Web Conference (ISWC 2006). Springer-Verlag
Lecture Notes in Computer Science Vol.4273, pp. 72-86.
Bao, J., Caragea, D., and Honavar,
V. (2006). Modular Ontologies - A Formal Investigation
of Semantics and Expressivity. In Proceedings of the
First Asian Semantic Web Conference, Beijing, China,
Springer-Verlag Lecture Notes in Computer Science,
Vol. 4185, pp. 616-631, 2006. Best Paper Award.
Pathak, J., Basu, S., Lutz, R., and
Honavar, V. (2006).Selecting and Composing Web Services
Through Iterative Reformulation of Functional Specifications.
Proceedings of the IEEE International Conference on
Tools With Artificial Intelligence (ICTAI 2006), Washington,
DC, IEEE. Best Paper Award.
Silvescu, A. and Honavar, V. (2006)
Independence, Decomposability and functions which
take values into an Abelian Group. Proceedings of
the Ninth International Symposium on Artificial Intelligence
and Mathematics, 2006.
Terribilini, M., Lee, J-H., Yan,
C., Honavar, V. and Dobbs, D. (2006). Identifying
Interactions in "Recalcitrant" Proteins. Predicted
Protein and RNA binding sites in REV proteins of HIV
and EIAV agree with experimental data. In: Proceedings
of the Pacific Symposium on Biocomputing, Hawaii,
World Scientific. Vol. 11. pp. 415-426.
Terribilini, M., Lee, J.H., Yan,
C., Jernigan, R., Honavar, V., and Dobbs, D. (2006).
Computational Prediction of Protein-RNA Interfaces.
RNA Journal.. Vol. 12. No. 1450. pp. 1462, 2006.
Yan, C., Terribilini, M.,Wu, F.,
Jernigan, R.L., Dobbs, D. and Honavar, V. (2006).
Identifying amino acid residues involved in protein-DNA
interactions from sequence. BMC Bioinformatics. Vol.
7. pp. 262-, 2006.
Zhang, J., Silvescu, A., Kang, D-K.,
and Honavar, V. (2006). Learning Compact and Accurate
Naive Bayes Classifiers from Attribute Value Taxonomies
and Partially Specified Data. Knowledge and Information
Systems. Vol. 9. No. 2. pp. 157-179, 2006.
Caragea, D., Zhang, J., Bao, J.,
Pathak, J., and Honavar, V. (2005). Algorithms and
Software for Collaborative Discovery from Autonomous,
Semantically Heterogeneous, Distributed, Information
Sources. Invited paper. In: Proceedings of the Conference
on Algorithmic Learning Theory. Lecture Notes in Computer
Science. Vol. 3734. Berlin: Springer-Verlag. pp. 13-44.
Yakhnenko, O., Silvescu, A., and
Honavar, V. (2005). Discriminatively Trained Markov
Model for Sequence Classification. In: Proceedings
of the IEEE Conference on Data Mining (ICDM 2005).
IEEE Press. pp. 498-505.
Zhang, J. and Honavar, V. (2003).
Learning Decision Tree Classifiers from Attribute-Value
Taxonomies and Partially Specified Data. In: Proceedings
of the International Conference on Machine Learning.
Washington, DC. AAAI Press. pp. 880-887.
Parekh, R. and Honavar, V. (2001).
Learning DFA from Simple Examples. Machine Learning.
Vol. 44. pp. 9-35.
XIAOQIU
HUANG, Associate Professor of Computer Science
Ph.D. 1990, Computer Science, Pennsylvania
State University
Major Interests:
Bioinformatics and computational
biology: design and applications of computational
methods for understanding the structure and evolution
of genomes.
Current Research:
The long term goal of Dr. Huang's
research is to develop computational methods for finding
functional elements in genomes. He has worked on two
major problems: genome assembly and alignment.
Genome Assembly
Dr. Huang and collaborators at Genome
Sequencing Center (GSC) of Washington University in
St. Louis have developed a packaged named PCAP for
reconstructing long genome sequences from short DNA
sequences generated in whole-genome shotgun sequencing
projects. The PCAP package has been used at GSC in
a number of large-scale genome sequencing projects
including the chimpanzee and chicken genome projects.
Dr. Huang has also developed a sequence assembly program
named CAP3.The CAP3 program has been used in thousands
of academic labs for assembly of sequences from gene
coding regions of the genome. PCAP and CAP3 are freely
available for academic use at http://seq.cs.iastate.edu.
Genome assembly is a challenging
computational problem. An input data set from a mammalian
genome consists of up to 40 millions of sequences
with a total size of 30 GB. A genome assembly program
takes several days to produce a draft assembly from
the input data set on hundreds of processors. Dr.
Huang and collaborators continue to make accuracy
and efficiency improvements to the PCAP package and
to develop computational methods for sequence data
from new genome sequencing technology.
Genome Alignment
Once the DNA sequence of a genome
is determined, computational methods are used to find
genes and regulatory elements in the genome. A very
effective computational method for finding genes and
regulatory elements in the genome is to compare the
new genome sequence with existing genome sequences
from other species, where similar regions between
the new genome and existing genomes are located and
aligned. The genome alignment method is based on the
evolutionary law that genes and regulatory elements
in the genomes of related species are much more conserved
than the other regions of the genomes.
Dr. Huang and collaborators have
designed a number of alignment algorithms and implemented
the algorithms in computer programs available to biologists
for analysis of DNA and protein sequences. A program
named SIM computes a number of optimal local alignments
between two sequences in linear space. The SIM program
has been used in thousands of academic labs for analysis
of protein sequences. A program named GAP3 is based
on a dynamic programming algorithm specially designed
to handle introns in genomic DNA sequences. Fast comparison
programs based on a lookup table or a superword array
(an efficient variation of a suffix array) have been
developed by Dr. Huang and collaborators.
A package named AAT of alignment
and comparison programs has been used for many years
at The Institute for Genomic Research for finding
genes in a genome. Many of the programs can be used
at http://deepc2.psi.iastate.edu/aat/sas.html. Dr.
Huang and collaborators continue to design better
alignment models and algorithms for producing genome
alignments.
See http://www.cs.iastate.edu/~xqhuang
for details.
Representative Publications:
Huang, X., Yang, S.-P., Chinwalla,
A., Hillier, L., Minx, P., Mardis, E. and Wilson,
R.(2006). Application of a Superword Array in Genome
Assembly. Nucleic Acids Research, 34:201-205.
Wang, J. and Huang, X.(2005). A Method
for Finding Single-Nucleotide Polymorphisms with Allele
Frequencies in Sequences of Deep Coverage. BMC Bioinformatics,
6:220.
Ye, L. and Huang, X.(2005). MAP2:
Multiple Alignment of Syntenic Genomic Sequences.
Nucleic Acids Research, 33:162-170.
Huang, X., Ye, L., Chou, H.-H., Yang,
I-H. and Chao, K.-M.(2004). Efficient Combination
of Multiple Word Models for Improved Sequence Comparison.
Bioinformatics, 20:2529-2533.
Huang, X., Wang, J., Aluru, S., Yang,
S.-P. and Hillier, L. (2003). PCAP: A Whole-Genome
Assembly Program. Genome Research, 13:2164-2170.
Huang, X. and Chao, K.-M. (2003).
A Generalized Global Alignment Algorithm. Bioinformatics,
19:228-233.
Huang, X, and Madan, A. (1999). CAP3:
A DNA Sequence Assembly Program. Genome Research,
9:868-877.
Huang, X, Adams, M.D., Zhou, H.,
and Kerlavage, A.R. (1997). A Tool for Analyzing and
Annotating Genomic Sequences. Genomics, 46:37-45.
Huang, X., and Zhang, J. (1996).
Methods for Comparing a DNA Sequence with a Protein
Sequence. Computer Applications in the Biosciences.
12:497-506.
Huang, X. and Miller, W. (1991) A
Time-Efficient, Linear-Space Local Similarity Algorithm.
Advances in Applied Mathematics, 12:337-357.
YAN-BIN
JIA, Associate Professor of Computer Science
Ph.D. 1997, Robotics (and Computer
Science), Carnegie Mellon University
Major Interests:
Robotics and artificial intelligence,
geometric algorithms for curves and surfaces, tactile
shape recognition and reconstruction, sensor implementation,
localization and robot sensing, computational geometry
and modeling, planning and control for robot dexterity,
robot interfaces, optimization, nonlinear control
and observation, kinematics and dynamics of manipulation.
Current Research:
Dr. Jia's main research objective
is to develop algorithms that would enable arobot
to effectively execute real world tasks that involve
sensing, localizing, grasping, and manipulating of
physical objects. His investigation into robot dexterity
has focused on understanding computational and control
issues in manipulation tasks. A major of this study
is the development of algorithms for dynamic retrieval
of geometric information such as shape and pose, and
of mechanical information such as motion and force,
and the effective use of such information in executing
specific tasks.
Dr. Jia has been studying the localization,
recognition, and reconstruction of curved shapes using
minimum tactile information. This study is aimed at
understanding the basic computational principles and
limitations of touch sensing. From a more general
perspective, he is interested in the design of geometric
and control algorithms for dexterous manipulation
and strategies for robot sensing that are efficient,
reliable, and easily integrable into manipulation
operations.
Details of Dr. Jia's research can
be found at http://www.cs.iastate.edu/~jia
Representative Publications:
Ibrayev, R.and Jia, Y-B.(2006). Surface
recognition by registering data curves from touch.Accepted
to the IEEE/RSJ International Conference on Intelligent
Robots and Systems, Beijing, PRC, Oct 9-15, 2006.
Jia, Y-B,Mi, L. and Tian, J. (2006).
Surface patch reconstruction via curve sampling. In
Proceedings of the IEEE International Conference on
Robotics and Automation, pp. 1371-1377, Orlando, FL,
May 16-18, 2006.
Ibrayev, R.and Jia, Y-B.(2005). Semi-differential
invariants for tactile recognition of algebraic curves.
International Journal of Robotics Research, vol. 24,
no. 11, pp. 951-969.
Jia, Y-B. (2005). Localization of
curved parts through continual touch. IEEE Transactions
on Robotics, vol. 21, no. 4, pp. 726-733.
Jia, Y-B. (2004). Computation on
parametric curves with an application in grasping.
International Journal of Robotics Research, vol. 23,
no. 7-8, pp. 825-855.
Jia, Y-B. andMi, L. (2004). High
precision contour tracking with a joystick sensor.
In Proceedings of the IEEE/RSJ International Conference
on Intelligent Robots and Systems, pp. 804-809, Sendai,
Japan, Sep 28 - Oct 2, 2004.
Jia, Y-B. (2003). Contact sensing
for parts localization: sensor design and experiments.
In Proceedings of the IEEE/RSJ International Conference
on Intelligent Robots and Systems, pp. 516-522, Las
Vegas, NV, Oct 27-31, 2003.
Jia, Y-B. and Erdmann, M. (1999).Pose
and Motion from Contact. International Journal of
Robotics Research, 18(5):466-490.
Jia, Y-B. and Erdmann, M. (1998).Local
Observability of Rolling. In Robotics: The Algorithmic
Perspective, P.K. Agarwal et al. (eds.), pp. 251-263,
A. K. Peters, Boston.
Jia, Y-B. and Erdmann, M. (1996).
Geometric Sensing of Known Planar Shapes. International
Journal of Robotics Research, 15(4):365-392.
GARY
T. LEAVENS, Professor of Computer Science.
Ph.D. 1989, Computer Science, Massachusetts
Institute of Technology
Major Interests:
Programming and specification language
design and semantics, formal methods (program specification
and verification), aspect-oriented languages, object-oriented
languages, distributed languages, type theory, programming
methodology, information assurance, computer science
education.
Current Research:
The long term goal of Dr. Leavens'
research is to understand better how to solve programming
problems: how to specify such problems, methods for
thinking about such problems, notations for expressing
solutions, ways to check that the solutions are correct,
and tools for automating and assisting with these
processes. In pursuing this goal, he has worked in
two main areas: formal methods and programming languages.
Dr. Leavens' work in formal methods
has been focused on ways to specify and verify object-oriented
(OO) software components. The specification work involves
the design and formal description of behavioral interface
specification languages (BISLs).BISLs record information
about detailed design: the interfaces and functional
behavior of program modules.Dr. Leavens's group has
designed a BISL for Smalltalk, called Larch/Smalltalk,
a BISL for C++, called Larch/C++, and, a BISL for
Java called JML (see www.jmlspecs.org). Current work
focuses on JML, and is being pursued as part of a
collaborative effort involving an international team
of researchers, in addition to people at ISU. Much
of this work centers around the problem of how to
make it expressive enough for documenting existing
code, as measured using both theoretical analysis
and case studies.
Dr. Leavens' work in the area of
formal methods for software components, is focused
on behavioral subtyping. Behavioral subtyping allows
one to reason about OO programs that use message passing.
The message passing mechanism of OO languages, such
as C++ and Java, allows one to easily extend programs
by adding new types.This works best if objects of
the new types behave like the objects of the old types;
the old types are supertypes of the new types, which
are called subtypes. How should one reason about programs
that use subtyping and message passing?Ideally, a
reasoning method, should be "modular" in
the sense that when subtypes are added to a program,
unchanged modules do not have to be respecified or
reverified. Modular reasoning is guaranteed by the
technique of supertype abstraction, which relies on
behavioral subtyping. To use supertype abstraction,
one specifies and verifies code in terms of the static
types of expressions written in a program (as usual),
uses a type checker to ensure that the static types
are supertypes of the run-time types, and then must
prove that subtypes obey the specifications of their
supertypes. This last condition is behavioral subtyping.
Dr. Leavens' work with Krishna Kishore Dhara, his
former Ph.D. student, has extended the formal theory
of behavioral subtyping to types whose instances have
time-varying state.Professor Don Pigozzi (now retired
from the Mathematics Department at ISU) and Leavens
have found an exact algebraic characterization of
behavioral subtyping for immutable types.They have
been working on effective techniques for proving behavioral
subtyping. Recent work with David Naumann (of Stevens)
on behavioral subtyping has precisely characterized
modular reasoning (supertype abstraction) for Java-like
languages.
The other main aspect of Dr. Leavens'
work has been on the design and semantics of object-oriented
languages with generic functions.Such languages are
known as multimethod programming languages, because
method calls can dispatch a message send on all arguments,
unlike a single-dispatching OO language, such as Smalltalk,
C++, or Java. Multimethod languages are interesting
because they can more easily express solutions to
certain problems in OO programming (binary methods).
Leavens' work on multimethod languages
in collaboration with Ph.D. student Curtis Clifton,
and Craig Chambers of the University of Washington,
and Chambers's student Todd D. Millstein focuses on
the semantics and type systems for variants of the
Cecil and Java languages. This work has led to an
algorithm for type checking such languages with very
expressive features (orthogonal inheritance and subtyping),
and results on how to add multimethods to existing
languages, and a way to add multimethods to Java.
These ideas have been applied in the design of an
extension to the Java programming language called
MultiJava (see www.multijava.org).A long term goal
is a language that allows one to program abstract
data types in two styles, one of which is easier to
extend (as in standard OO languages) and the other
of which is easier to reason about. Programmers can
use both styles in the same program. Another goal
is to extend the kind of modular programming and reasoning
techniques that apply to MultiJava to aspect-oriented
programs.The potential impact of these research directions
might be large if this leads to more flexible, modular,
and reusable coding practices.
Details of Dr. Leavens' research
can be found at http://www.cs.iastate.edu/~leavens/.
Representative Publications:
Mueller, P., Poetzsch-Heffter, A.
and Leavens, G. (2006). Modular Invariants for Layered
Object Structures.Science of Computer Programming,
62(3):253-286.
Clifton, C., Millstein, T., Leavens,
G. and Chambers, C. (2006). MultiJava: Design Rationale,
Compiler Implementation, and Applications. ACM TOPLAS,
28(3):517-575.
Leavens, G., Cheon, Y., Clifton,
C., Ruby, C. and Cok, D. (2005). How the design of
JML accommodates both runtime assertion checking and
formal verification. Science of Computer Programming,
55(1-3):185-205.
Mueller, P., Poetzsch-Heffter, A.
and Leavens, G. (2003). Modular Specification of Frame
Properties in JML. Concurrency and Computation: Practice
and Experience, 15(2):117-154, February, 2003.
Cheon, Y.and Leavens, G. (2002).
A Simple and Practical Approach to Unit Testing: The
JML and JUnit Way. In Boris Magnusson (ed.), ECOOP
2002 - Object-Oriented Programming, 16th European
Conference, Malaga, Spain, June 2002, Proceedings.
Volume 2374 of Lecture Notes in Computer Science,
Springer-Verlag, pages 231-255.
Ruby, C.and Leavens, G. (2000). Safely
Creating Correct Subclasses without Seeing Superclass
Code. In OOPSLA 2000 Conference Proceedings, pages
208-228. Volume 35, number 10 of ACM SIGPLAN Notices,
October.
Clifton, C., Leavens, G., Chambers,
C., and Millstein, T. (2000). MultiJava: Modular Open
Classes and Symmetric Multiple Dispatch for Java.
In OOPSLA 2000 Conference Proceedings, pages 130-145.
Volume 35, number 10 of ACM SIGPLAN Notices, October
2000.
Leavens, G. and Pigozzi, D. (2000).
A complete algebraic characterization of behavioral
subtyping. Acta Informatica, 36:617-663.
Leavens, G.and Dhara, K. (2000).
Concepts of Behavioral Subtyping and a Sketch of their
Extension to Component-Based Systems. In Gary T. Leavens
and Murali Sitaraman (editors), Foundations of Component-Based
Systems, Cambridge University Press. Chapter 6, pages
113-135.
Leavens, G. and Wing, J. (1998).
Protective Interface Specifications. Formal Aspects
of Computing, 10:59-75.
JACK
H. LUTZ, Professor of Computer Science
Ph.D. 1987, Mathematics, California
Institute of Technology
Major Interests:
Computational Complexity: structure
of complexity classes, resource-bounded measure and
dimension, and complexity in analysis. Algorithmic
Information and Randomness: computational randomness,
constructive dimension, Kolmogorov complexity, prediction,
finite-state dimension, and algorithmic fractal geometry.
Nanoscale Self-Assembly: information flow, universal
computation, zeta-dimension, and randomness in self-assembling
fractal structures.
Current Research:
Dr. Lutz is currently focused on
computational complexity, algorithmic information
theory, and nanoscale self-assembly. In all three
of these areas, I collaborate extensively with graduate
students, postdoctoral researchers, and faculty, both
at ISU and elsewhere.In computational complexity he
is investigating the structure of complexity classes
(deterministic, non-deterministic, and probabilistic)
using resource-bounded measure and dimension, complexity-theoretic
generalizations of Lebesgue measure and fractal dimension
that he has developed.
Current work focuses on derandomization,
weak completeness, circuit-size complexity, strong
hypotheses, and the type-2 foundations of resource-bounded
measure and dimension.We are also investigating computability
and complexity in geometric measure theory, which
is the part of mathematical analysis that deals with
the fine-scale properties of fractals, particle trajectories,
and other dynamical processes in real Euclidean space.
In algorithmic information theory
Dr. Lutz is studying randomness,Kolmogorov complexity,
and constructive dimension, with applications in algorithmic
prediction, geometric measure theory, and games. His
research group isalso investigating finite-state dimension,
especially in connection with Borel normal numbers
and data compression. Their newest research area is
nanoscale self-assembly.Here they are investigating
the algorithmic self-assembly of fractal structures
in the DNA tile assembly model of Seeman, Winfree,
and Rothemund.They are especially interested in zeta-dimension,
which is the appropriate measure of the fractal dimensions
of such structures; bandwidth as a physical complexity
measure; the apparent tradeoff between zeta-dimension
and efficiency of computation in self-assembly; and
randomized self-assembly.
Representative Publications:
Gu, X., Lutz, J. and Mayordomo, E.
(2006). "Points on Computable Curves", Proceedings
of the the Forty-Seventh Annual IEEE Symposium on
Foundations of Computer Science (Berkeley, CA, October
22-24, 2006), IEEE Computer Society Press, pp. 469-474.
Doty, D., Lutz, J., and Nandakumar,
S. (2006). "Finite-State Dimension and Real Arithmetic",
Proceedings of the Thirty-Third InternationalColloquium
on Automata, Languages, and Programming} (Venice,
Italy, July 10-14, 2006), Springer-Verlag, pp. 537-547.
Gu, X.and Lutz, J."Dimension
Characterizations of Complexity Classes", Computational
Complexity, to appear.
Gu, X., Lutz, J. and Moser, P."Dimensions
of Copeland-Erdos Sequences", Information and
Computation, In press.
Athreya, K., Hitchcock,J., Lutz,
J. and Mayordomo, E. "Effective Strong Dimension
in Algorithmic Information and Computational Complexity",
SIAM Journal on Computing, In press.
Hitchcock, J., Lutz, J. and Terwijn,
S. (2007). "The Arithmetical Complexity of Dimension
and Randomness", ACM Transactions on Computational
Logic, In press.
Hitchcock, J. and Lutz, J. (2006).
"Why Computational Complexity Requires Stricter
Martingales", Theory of Computing Systems 39,
pp. 277-296.
Fortnow, L.and Lutz, J. (2005). "Prediction
and Dimension", Journal of Computer and System
Sciences 70, pp. 570-589.
Hitchcock, J., Lutz, J. and Mayordomo,
E. (2004). "Scaled Dimension andNonuniform Complexity",
Journal of Computer and System Sciences 69, pp. 97-122.
Dai, J., Lathrop, J., Lutz, J.and
Mayordomo, E. (2004). "Finite-State Dimension",
Theoretical Computer Science 310, pp. 1-33.
Lutz, J. (2003)."The Dimensions
of Individual Strings and Sequences", Information
and Computation 187, pp. 49-79.
Lutz, J. (2003)."Dimension in
Complexity Classes", SIAM Journal on Computing
32, pp. 1236-1259.
ROBYN
LUTZ, Professor of Computer Science
Ph.D. 1980, Spanish, University of
Kansas
M.S. 1990, Computer Science, Iowa
State University
Major Interests:
Safety-critical product lines, requirements
engineering, software safety, formal methods for specification
and analysis, fault monitoring and recovery, software
engineering.
Current Research:
Dr. Lutz's research is in software
engineering, the part of computer science that studies
how to develop better software systems. Her research
contributions have been in two overlapping areas of
software engineering:(1) how to build safe systems
and (2) how to specify and analyze requirements for
those systems.
Safety-critical software is software
that can cause, or prevent, a hazardous situation
or damage to life, property, or mission. Examples
of safety-critical software include the software in
medical imaging systems, in autonomous vehicles, and
in spacecraft control systems. Dr. Lutz's research
in the area of software safety has focused on safety-critical
software product lines.A product line is a set of
highly similar systems with a few key variations.
Some examples of safety-critical software product
lines that she has worked with are: flight-instrumentation
displays (such as pilots use in the cockpit), interferometers
(spaceborne, astronomical telescopes), medical-imaging
systems (used by physicians to create computer images
of patients' organs), and implantable medical devices
(such as pacemakers and defibrillators).Dr. Lutz's
key contributions in this area have been to extend
software-safety techniques that were traditionally
applied only to single systems to handle the new product
lines of systems. The purpose of these extensions
is to allow safety analyses to become reusable assets
within a product line. By expanding software-safety
techniques to product lines, and by formalizing the
caveats on such reuse, Dr. Lutz and her research group
hope to reduce the cost of doing safety analysis on
product lines and speed up time-to-market of new products
in the line. More importantly for safety-critical
product lines, these techniques enhance the thoroughness
and rigor of the safety analyses performed.
Dr. Lutz's work on requirements analysis
for safety critical systems has focused on methods
that enable developers to more accurately describe
and rigorously analyze the requirements and design
for safety-critical software. Historically, many failures
of software have been due to an inadequate understanding
of the software requirements by the developers. The
specifications of what the software had to do were
incomplete or inconsistent in some way that hindered
safe, correct software from being built.One of Dr.
Lutz's key contributions in this area has been to
create formal models for the fault-protection software
that detects and isolates system failures, and reconfigures
the system to recover from them. More recently, she
and collaborators at Jet Propulsion Laboratory and
NASA Ames have developed a tool-supported, development
approach for diagnosing and responding to contingencies
(operational situations with mission risk) in a formal
model of an unpiloted aerial vehicle.
A second key contribution has been
the development by Dr. Lutz of Bi-Directional Safety
Analysis, which systematically combines two distinct
analysis methods to search for missing or incomplete
requirements in software systems. Many of the results
in this area have been applied to NASA spacecraft.
With support from the NSF, Dr. Lutz and her students
have extended this technique to product lines. She
has also investigated a product-line approach to the
development of distributed multi-agent systems (such
as fleets of autonomous vehicles). Other collaborative
applications have been to automatic construction of
monitors for intrusion detection and to guiding user
goal-refinement when a desired web-service composition
fails.
A third key contribution has been
to empirically confirm what was long-suspected:that
misunderstood requirements and interfaces cause failures
during testing and operations. Dr. Lutz and Carmen
Mikulsi did this by identifying and describing the
patterns of requirements omissions and requirements
misunderstandings that escaped testing to manifest
themselves during flight. These empirical investigations
enabled the pinpointing of some specific, common weaknesses
in the software requirements specification process.
Dr. Lutz, in collaboration with her students, has
developed solutions that target these specific areas.
Supported by NSF, Dr. Lutz's research group and Dr.
John Knight's research group at the University of
Virginia have experimentally applied automated analysis
results from software problem reports (generated during
testing) to iteratively improve the linguistic domain
modeling of requirements specifications.
Additional details of Dr. Lutz's
research can be found at www.cs.iastate.edu/~rlutz
Representative Publications:
Lutz, R., Patterson-Hine, A., Nelson,
S., Frost, C., Tal, D., and Harris, R."Using Obstacle
Analysis to Identify Contingency Requirements on an
Unpiloted Aerial Vehicle", Requirements Engineering
Journal, to appear.
Lutz, R., Patterson-Hine, A., and
Bajwa, A. "Tool-Supported Verification of Contingency
Software Design in Evolving, Autonomous Systems",
Proc. 7th IEEE International Symposium on Software
Reliability Engineering (ISSRE 2006). Nov. 7-10, 2006,
Raleigh, NC.
Dehlinger, J. and Lutz, R. (2006).
"PLFaultCat:A Product-Line Software Fault Tree Analysis
Tool", Automated Software Engineering, 13(1): pp.
169-193.
Dehlinger, J. and Lutz, R. (2005).
"A Product-Line Approach to Promote Asset Reuse in
Multi-Agent Systems", SELMAS 2005, LNCS vol. 3914,
Ed. R. Choren.
Feng, Q. and Lutz, R.. "Bi-Directional
Safety Analysis of Product Lines", Journal of Systems
and Software, 78(2), Nov. 2005, pp. 111-127.
Padmanabhan, P. and Lutz, R.. "Tool-Supported
Verification of Product Line Requirements, Automated
Software Engineering, 12(4), Oct., 2005, pp. 447-485.
Schwanke, R. and Lutz, R.. "Experience
with Architectural Design of a Modest Product Family,"
Software Practice and Experience, 34(13), Nov. 2004,
pp. 1273-1296.
Lutz, R. and Mikulski, C. "Empirical
Analysis of Safety-Critical Anomalies during Operations,"
IEEE Transactions on Software Engineering," vol. 30,
no., 3, March, 2004, pp. 172-180.
Lutz,R. (2000). "Software Engineering
for Safety:A Roadmap,'' in The Future of Software
Engineering, 2000, ed. A. Finkelstein, ACM,Invited
Chapter, pp. 213-224.
Easterbrook, S., Lutz, R., Covington,
'R., Kelly, J.,Ampo, Y. and Hamilton, D. "Experiences
Using Lightweight Formal Methods for Requirements
Modeling," IEEE Transactions on Software Engineering,
Vol. 24, 1, Jan., 1998, pp. 4-14.
Lutz, R. and Wong, J. "Detecting
Unsafe Error Recovery Schedules,'' IEEE Transactions
on Software Engineering, Vol. 18, 8, Aug., 1992, pp.
749-760.
DIMITRIS
MARGARITIS, Assistant Professor of Computer Science
Ph.D. 2003, Computer Science, Carnegie
Mellon University
Major Interests:
Probabilistic modeling, methods for
managing and reasoning with uncertainty/indeterminacy
in Artificial Intelligence and other applications,
Bayesian networks, Markov networks, data mining, machine
learning, cross-disciplinary applications of these
in bioinformatics, econometrics, very large databases
and other domains.
Current Research:
Dr. Margaritis's current research
is on algorithms for learning the structure of Bayesian
networks and applying them to real-world application
domains where modeling uncertainty might be beneficial.For
example, it turns out that approximate query answering
in very large databases can be done quickly using
a sufficiently complex model of the database---in
this case a Bayesian network. He would also like to
explore capturing and modeling information about influences
by statistical means in bioinformatics domains such
as protein structure prediction. Dr. Margaritis's
long-term vision is to develop algorithms and representations
that help researchers gain insights into their research
domains by automatically constructing probabilistic
models of them from data.
Representative Publications:
Bromberg, F., Margaritis, D. and
Honavar, V. (2006). Efficient Markov Network Structure
Discovery from Independence Tests.SIAM International
Conference on Data Mining (SDM).
Margaritis, D. (2005). Distribution-Free
Learning of Bayesian Network Structure in Continuous
Domains.National Conference on Artificial Intelligence
(AAAI).
Yaramakala, S. and Margaritis, D.
(2005). Speculative Markov Blanket Discovery for Optimal
Feature Selection.IEEE International Conference on
Data Mining (IEEE ICDM).
Cheng, H., Sen, T. Z. , Kloczkowski,
A., Margaritis, D.and Jernigan, R. L.. Prediction
of Protein Secondary Structure by Mining Fragments
Database, Polymer.in press.
Margaritis, D. and Thrun, S. (2001).
A Bayesian Multiresolution Independence Test for Continuous
Variable. Uncertainty in Artificial Intelligence (UAI).
Margaritis, D., Faloutsos, C. and
Thrun, S. (2001). NetCube: A Scalable Tool for Fast
Data Mining and Compression. International Conference
on Very Large Databases (VLDB).
Margaritis, D. and Thrun, S. (1999).
Bayesian Network Induction via Local Neighborhoods.
Neural Information Processing Systems (NIPS).
Moghaddam, D., Biermann, H. and Margaritis,
D. (2001). Regions-of-Interest and Spatial Layout
for Content-Based Image Retrieval. Journal of Multimedia
Tools and Applications, Kluwer Academic Publishers,
Vol. 14, No. 3, 2001.
Margaritis, D. and Thrun, S. (1998).
Learning to Locate and Object in 3D Space from a Sequence
of Camera Images. International Conference in Machine
Learning (ICML).
Waldherr, S., Thrun, S.,Romero, R.
and Margaritis, D. (1998). Template-Based Recognition
of Pose and Motion Gestures on a Mobile Robot. National
Conference on Artificial Intelligence (AAAI).
LES
MILLER, Professor of Computer Science
Ph.D. 1980, Computer Science, Southern
Methodist University
Research Areas
Bioinformatics and Computational
Biology, e-Government, Human Computer Interaction,
Data Warehouses, Information Integration and Information
Retrieval, Database Systems, Information Security,
Software Systems
Research Statement
Dr. Miller's current research is
focused on interface design issues for handheld computers
used in spatial data collection within Bureau of Census's
decennial census. Other current work in human computer
interaction aims to enhance the use of the Internet
by the elderly. His workin computational biology is
focused onthe development of graph models for storing
and analyzing biological networks.His on knowledge
Management looks at the development of distributed
knowledge management systems that use business process-based
topic maps as knowledge hubs. Work on organizational
memory is focused on the capture of organizational
semantics and the integration of memory artifacts
into the organization's knowledge base.
Selected Publications
Miller, L., Nilakanta, S., Song,
Y., Zhu, L. and Hua, M. (2007). Knowledge Management:
Using Topic Maps in Organizational Memory. Hawaiian
International Conference on System Sciences.pp. 204b-
Miller, L., Ding, J. and Nusser,
S. (2007). An Accuracy Model for Relational Databases.
Accepted to the ISCA 22nd International Conference
on Computers and Their Applications. In press.
Nilakanta, S., Miller, L., Song,
Y. and Zhu, L. (2007). Supporting Topic Maps in an
Organizational Memory Web Server. Information Resources
Management Association International Conference.In
press.
Helmer, G., Wong, J., Slagell, M.,
Honavar, V., Miller, L., Wang, Y., Wang, X. and Stakhanova,
N. (2007). Software Fault Tree and Colored Petri Net
Based Specification, Design and Implementation of
Agent-Based Intrusion Detection Systems. To appear
in the International Journal of Information and Computer
|
