Efficient Computation of k-Medians over Data Streams Under Memory Constraints

In this paper, we study the problem of efficiently computing k-medians over high-dimensional and high speed data streams. The focus of this paper is on the issue of minimizing CPU time to handle high speed data streams on top of the requirements of high accuracy and small memory. Our work is motivated by the following observation： the existing algorithms have similar approximation behaviors in practice, even though they make noticeably different worst case theoretical guarantees. The underlying reason is that in order to achieve high approximation level with the smallest possible memory, they need rather complex techniques to maintain a sketch, along time dimension, by using some existing off-line clustering algorithms. Those clustering algorithms cannot guarantee the optimal clustering result over data segments in a data stream but accumulate errors over segments, which makes most algorithms behave the same in terms of approximation level, in practice. We propose a new grid-based approach which divides the entire data set into cells （not along time dimension）. We can achieve high approximation level based on a novel concept called （1 - ε）-dominant. We further extend the method to the data stream context, by leveraging a density-based heuristic and frequent item mining techniques over data streams. We only need to apply an existing clustering once to computing k-medians, on demand, which reduces CPU time significantly. We conducted extensive experimental studies, and show that our approaches outperform other well-known approaches.     

Behavior of the Laplacian of Gaussian Extrema

This paper analyses the behavior in scale space of linear junction models (L, Y and X models), nonlinear junction models, and linear junction multi-models. The variation of the grey level is considered to be constant, linear or nonlinear in the case of linear models and constant for the other models. We are mainly interested in the extrema points provided by the Laplacian of the Gaussian function. Moreover, we show that for infinite models the Laplacian of the Gaussian at the corner point is not always equal to zero.Salvatore Tabbone received his Ph.D. in computer science from the Institut National Polytechnique de Lorraine (France) in 1994. He is currently an assistant professor at the University of Nancy2 (France) and a member of the QGAR research project on graphics recognition at the LORIA-INRIA research center. His research interests include computer vision, pattern recognition, content-based image retrieval, and document analysis and recognition.Laurent Alonso was a student of ENS Ulm from 1987 to 1991, he received the Ph.D. degree in Computer Science from the University of Paris XI, Orsay, France in 1992. From 1991 to 1995 he served as lecturer in the University of Nancy I (France). Actually, he is full researcher in INRIA (France). His research interests include realistic rendering, geometric algorithms and combinatorics.Djemel Ziou received the BEng Degree in Computer Science from the University of Annaba (Algeria) in 1984, and Ph.D. degree in Computer Science from the Institut National Polytechnique de Lorraine (INPL), France in 1991. From 1987 to 1993 he served as lecturer in several universities in France. During the same period, he was a researcher in the Centre de Recherche en Informatique de Nancy (CRIN) and the Institut National de Recherche en Informatique et Automatique (INRIA) in France. Presently, he is full Professor at the department of computer science at the University of Sherbrooke in Canada. He has served on numerous conference committees as member or chair. He heads the laboratory MOIVRE and the consortium CoRIMedia which he founded. His research interests include image processing, information retrieval, computer vision and pattern recognition.     

Recent Progress on Selected Topics in Database Research ——-A Report by Nine Young Chinese Researchers Working in the United States

The study on database technologies, or more generally, the technologies of data and information management, is an important and active research field. Recently, many exciting results have been reported. In this fast growing field, Chinese researchers play more and more active roles. Research papers from Chinese scholars, both in China and abroad,appear in prestigious academic forums.In this paper,we, nine young Chinese researchers working in the United States, present concise surveys and report our recent progress on the selected fields that we are working on.Although the paper covers only a small number of topics and the selection of the topics is far from balanced, we hope that such an effort would attract more and more researchers,especially those in China,to enter the frontiers of database research and promote collaborations. For the obvious reason, the authors are listed alphabetically, while the sections are arranged in the order of the author list.     

From Active to Passive—Progress in Testing Internet Routing Protocols

Routing protocols play an important role in the Internet and the test requirements are running up.To test routing protocols more efficiently,several enhancing techniques are applied in the protocol integrated test system described in this paper.The Implementation Under Test is modeled as a black box with windows.The test system is endowed with multiple channels and multiple ports to test distributed protocols.The test suite and other related aspects are also extended.Meanwhile,the passive testing is introduced to test,analyze and manage routing protocols in the production field,which is able to perform the conformance test,the interoperability test and the performance test.The state machine of peer sessions is tested with the state synchronization algorithm,and the routing information manipulation and other operations are checked and analyzed with the methods like the topology analysis and the internal process simulation,With both the active testing and the passive testing,the routing protool test is going further and more thoroughly and helps a lot in the developmnt of routers。     

ARMiner: A Data Mining Tool Based on Association Rules

In this paper,ARM iner,a data mining tool based on association rules,is introduced.Beginning with the system architecture,the characteristics and functions are discussed in details,including data transfer,concept hierarchy generalization,mining rules with negative items and the re-development of the system.An example of the tool‘s application is also shown.Finally,Some issues for future research are presented.     

Fast training for object recognition with structure-from-motion

In this paper we present a system for statistical object classification and localization that applies a simplified image acquisition process for the learning phase. Instead of using complex setups to take training images in known poses, which is very time-consuming and not possible for some objects, we use a handheld camera. The pose parameters of objects in all training frames that are necessary for creating the object models are determined using a structure-from-motion algorithm. The local feature vectors we use are derived from wavelet multiresolution analysis. We model the object area as a function of 3D transformations and introduce a background model. Experiments made on a real data set taken with a handheld camera with more than 2500 images show that it is possible to obtain good classification and localization rates using this fast image acquisition method. The text was submitted by the authors in English. Marcin Grzegorzek, born in 1977, obtained his Master’s Degree in Engineering from the Silesian University of Technology Gliwice (Poland) in 2002. Since December 2002 he has been a PhD candidate and member of the research staff of the Chair for Pattern Recognition at the University of Erlangen-Nuremberg, Germany. His fields are 3D object recognition, statistical modeling, and computer vision. He is an author or coauthor of seven publications. Michael Reinhold, born in 1969, obtained his degree in Electrical Engineering from RWTH Aachen University, Germany, in 1998. Later, he received a Doctor of Engineering from the University of Erlangen-Nuremberg, Germany, in 2003. His research interests are statistical modeling, object recognition, and computer vision. He is currently a development engineer at Rohde & Schwarz in Munich, Germany, where he works in the Center of Competence for Digital Signal Processing. He is an author or coauthor of 11 publications. Ingo Scholz, born in 1975, graduated in computer science at the University of Erlangen-Nuremberg, Germany, in 2000 with a degree in Engineering. Since 2001 he has been working as a research staff member at the Institute for Pattern Recognition of the University of Erlangen-Nuremberg. His main research focuses on the reconstruction of light field models, camera calibration techniques, and structure from motion. He is an author or coauthor of ten publications and member of the German Gesellschaft für Informatik (GI). Heinrich Niemann obtained his Electrical Engineering degree and Doctor of Engineering degree from Hannover Technical University, Germany. He worked with the Fraunhofer Institut für Informationsverarbeitung in Technik und Biologie, Karlsruhe, and with the Fachhochschule Giessen in the Department of Electrical Engineering. Since 1975 he has been a professor of computer science at the University of Erlangen-Nuremberg, where he was dean of the engineering faculty of the university from 1979 to 1981. From 1988 to 2000, he was head of the Knowledge Processing research group at the Bavarian Research Institute for Knowledge-Based Systems (FORWISS). Since 1998, he has been a spokesman for a “special research area” with the name of “Model-Based Analysis and Visualization of Complex Scenes and Sensor Data” funded by the German Research Foundation. His fields of research are speech and image understanding and the application of artificial intelligence techniques in these areas. He is on the editorial board of Signal Processing, Pattern Recognition Letters, Pattern Recognition and Image Analysis, and the Journal of Computing and Information Technology. He is an author or coauthor of seven books and about 400 journal and conference contributions, as well as editor or coeditor of 24 proceedings volumes and special issues. He is a member of DAGM, ISCA, EURASIP, GI, IEEE, and VDE and an IAPR fellow.     

A new algebraic modelling approach to distributed problem-solving in MAS

This paper is devtoed to a new algebraic modelling approach to distributed problem-solving in multi-agent systems(MAS),which is featured by a unified framework for describing and treating social behaviors,social dynamics and social intelligence.A coneptual architecture of algebraic modelling is presented.The algebraic modelling of typical social be-haviors,social situation and social dynamics is discussed in the context of distributed problem-solving in MAS .The comparison and simulation on distributed task allocations and resource assignments in MAS show more advantages of the algebraic approach than other conventional methods.     

PAN: A portable,parallel Prolog: Its design,realisation and performance

PAN is a general purpose, portable environment for executing logic programs in parallel. It combines a flexible, distributed architecture which is resilient to software and platform evolution with facilities for automatically extracting and exploiting AND and OR parallelism in ordinary Prolog programs. PAN incorporates a range of compile-time and run-time techniques to deliver the performance benefits of parallel execution while rertaining sequential execution semantics. Several examples illustrate the efficiency of the controls that facilitate the execution of logic programs in a distributed manner and identify the class of applications that benefit from distributed platforms like PAN. George Xirogiannis, Ph.D.: He received his B.S. in Mathematics from the University of Ioannina, Greece in 1993, his M.S in Artificial Intelligence from the University of Bristol in 1994 and his Ph.D. in Computer Science from Heriot-Watt University, Edinburgh in 1998. His Ph.D. thesis concerns the automated execution of Prolog on distributed heterogeneous multi-processors. His research interests have progressed from knowledge-based systems to distributed logic programming and data mining. Currently, he is working as a senior IT consultant at Pricewaterhouse Coopers. He is also a Research Associate at the National Technical University of Athens, researching in knowledge and data mining. Hamish Taylor, Ph.D.: He is a lecturer in Computer Science in the Computing and Electrical Engineering Department of Heriot-Watt University in Edinburgh. He received M.A. and MLitt degrees in philosophy from Cambridge University and an M.S. and a Ph.D. degree in computer science from Heriot-Watt University, Scotland. Since 1985 he has worked on research projects concerned with implementing concurrent logic programming languages, developing formal models for automated reasoning, performance modelling parallel relational database systems, and visualisizing resources in shared web caches. His current research interests are in applications of collaborative virtual environments, parallel logic programming and networked computing technologies.     

Printed Arabic character recognition using HMM

The Arabic Language has a very rich vocabulary. More than 200 million people speak this language as their native speaking, and over 1 billion people use it in several religion-related activities. In this paper a new technique is presented for recognizing printed Arabic characters. After a word is segmented, each character/word is entirely transformed into a feature vector. The features of printed Arabic characters include strokes and bays in various directions, endpoints, intersection points, loops, dots and zigzags. The word skeleton is decomposed into a number of links in orthographic order, and then it is transferred into a sequence of symbols using vector quantization. Single hidden Markov model has been used for recognizing the printed Arabic characters. Experimental results show that the high recognition rate depends on the number of states in each sample.     

Internet Network Resource Information Model

The foundation of any network management systems is a database that contains information about the network resources relevant to the management tasks.A network information model is an abstraction of network resources,including both managed resources and managing resources,In the SNMP-based management framework,management information is defined almost exclusively from a “Device“ viewpoint,namely managing a network is equivalent to managing a collection of individual nodes.Aiming at making use of recent advances in distributed computing and in object-oriented analysis and design,the Internet management architecture can also be based on the Open Distributed Processing Reference Model(RM-ODP).The purpose of this article is to provide an Internet Network Resource Information Model.First,a layered management information architecture will be discussed.Then the Internet Network resource information model is presented.The information model is specified using object-Z.     

Segmentation of convex cells with partially undefined edges

This paper presents an algorithm for segmentation of convex cells with partially undefined edges based on application of a marker-controlled watershed transform to a combination of a source grayscale image and the result of a “geodesic distance” morphological operation, applied to the result of binarization of a source image. The presented approach is used in computer image processing systems for analysis of several industrial materials. The text was submitted by the authors in English. Ilia V. Safonov received his MS degree in automatic and electronic engineering from Moscow Engineering Physics Institute/University (MEPhI), Russia in 1994 and his PhD degree in computer science from MEPhI in 1997. Since 1998 he is an associate professor of faculty of Cybernetics of MEPhI while conducting researches in image segmentation, features extraction and pattern recognition problems. Since 2004, Dr. I. Safonov has joint Image Enhancement Technology Group, Printing Technology Lab, Samsung Research Center, Moscow, Russia where he is engaged in photo, video, and document image enhancement projects. Konstantin A. Kryzhanovsky received the MS degree in cybernetics from Moscow Engineering Physics Institute/University (MEPhI), Russia in 2000. Since 2006 he is an assistant professor of faculty of Cybernetics of MEPhI. He is presently working towards his Ph.D. degree. His current research interests include image processing and pattern recognition. Gennady N. Mavrin received his MS degree in automatic and electronic engineering from Moscow Engineering Physics Institute/University (MEPhI), Russia in 1998. Since 2002 he is an assistant professor of faculty of Cybernetics of MEPhI. He is currently pursuing the PhD degree. His research interests include image segmentation and feature extraction problems.     

An Effective Randomized QoS Routing Algorithm on Networks with Inaccurate Parameters

This paper develops an effective randomized on-demand QoS routing algorithm on networks with inaccurate link-state information.Several new techniques are proposed in the algorithm.First,the maximum safety rate and the minimum delay for each node in the network are pre-computed,which simplicfy the network complexity and provide the routing process with useful information .The routing process is dynamically directed by the safety rate and the minimum delay of the next node.Randomness in used at the link level and depends dynamically on the routing configurationl.This provides great flexibility for the routing process,prevents the routing process from overusing certain fixed routing paths,and adequately balances the safety rate and delay of the routing path.A network testing environment has been established and five parameters are introduced to measure the performance of QoS routing algorithms.Experimental results demonstrate that in terms of the proposed parameters,the algorithm outperforms existing Qos algorithms appearing in the literature.     

P transducers

We introduce in this paper four classes of P transducers: arbitrary, initial, isolated arbitrary, isolated and initial. The first two classes are universal, they can compute the same word functions as Turing machines, the latter two are incomparable with finite state sequential transducers, generalized or not. We study the effect of the composition, and show that iteration increases the power of these latter classes, also leading to a new characterization of recursively enumerable languages. The “Sevilla carpet” of a computation is defined for P transducers, giving a representation of the control part for these P transducers. Gabriel Ciobanu, Ph.D.: He has graduated from the Faculty of Mathematics, “A.I.Cuza” University of Iasi, and received his Ph.D. from the same university. He is a senior researcher at the Institute of Computer Science of the Romanian Academy. He has wide-ranging interests in computing including distributed systems and concurrency, computational methods in biology, membrane computing, and theory of programming (semantics, formal methods, logics, verification). He has published around 90 papers in computer science and mathematics, a book on programming semantics and a book on network programming. He is a co-editor of three volumes. He has visited various universities in Europe, Asia, and North America, giving lectures and invited talks. His webpage is http://www.info.uaic.ro/gabriel Gheorghe Păun, Ph.D.: He has graduated from the Faculty of Mathematics, University of Bucharest, in 1974 and received his Ph.D. from the same university in 1977. Curently he works as senior researcher in the Institute of Mathematics of the Romanian Academy, as well as a Ramon y Cajal researcher in Sevilla University, Spain. He has repeatedly visited numerous universities in Europe, Asia, and North America. His main research areas are formal language theory and its applications, computational linguistics, DNA computing, and membrane computing (a research area initiated by him). He has published over 400 research papers (collaborating with many researchers worldwide), has lectured at over 100 universities, and gave numerous invited talks at recognized international conferences. He has published 11 books in mathematics and computer science, has edited about 30 collective volumes, and also published many popular science books and books on recreational mathematics (games). He is on the editorial boards of fourteen international journals in mathematics, computer science, and linguistics, and was/is involved in the program/steering/organizing commitees for many recognized conferences and workshops. In 1997 he was elected a member of the Romanian Academy. Gheorghe Ştefănescu, Ph.D.: He received his B.Sc./M.Sc./Ph.D. degrees in Computer Science from the University of Bucharest. Currently, he is a Professor of Computer Science at the University of Bucharest and a Senior Fellow at the National University of Singapore. Previously, he was a researcher at the Institute of Mathematics of the Romanian Academy and has held visiting positions in The Netherlands, Germany, and Japan. His current research focuses on formal methods in computer science, particularly on process and network algebras, formal methods for interactive, real-time, and object-oriented systems. Some of his results may be found in his book on “Network Algebra,” Springer, 2000.     

A Fast Scalable Classifier Tightly Integrated with RDBMS

In this pager,we report our success in building efficient scalable classifiers by exploring the capabilities of modern relational database management systems (RDBMS).In addition to high classification accuracy,the unique features of the approach include its high training speed ,linear scalability,and simplicity in implementation.More importantly,the major computation required in the approach can be implemented using standard functions provided by the modern realtional DBMS.Besides,with the effective rule pruning strategy,the algorithm proposed in this paper can produce a compact set of classification rules,The results of experiments conducted for performance evaluation an analysis are presented.     

On minimizing errors in 3D reconstruction for stereo camera systems

Active reconstruction of 3D surfaces deals with the control of camer a viewpoints to minimize error and uncertainty in the reconstructed shape of an object. In this paper we develop a mathematical relationship between the setup and focal lengths of a stereo camera system and the corresponding error in 3D reconstruction of a given surface. We explicitly model the noise in the image plane, which can be interpreted as pixel noise or as uncertainty in the localization of corresponding point features. The results can be used to plan sensor positioning, e.g., using information theoretic concepts for optimal sensor data selection. The text was submitted by the authors in English. Stefan Wenhardt, born in 1978, graduated in mathematics at the University of Applied Sciences, Regensburg, Germany, in 2002, with a degree of Dipl.-Math. (FH). Since June 2002, he has been a research staff member at the Chair for Pattern Recognition at the Friedrich-Alexander-University of Erlangen-Nuremberg, Germany. The topics of his research are 3D reconstruction and active vision systems. He is author or coauthor of four publications. Joachim Denzler, born April 16, 1967, received a degree of Diplom-Informatiker, Dr.-Ing. and Habilitation from the University of Erlangen in 1992, 1997, and 2003, respectively. Currently, he holds a position of a full professor for computer science and is head of the computer vision group, Faculty of Mathematics and Informatics, University of Jena. His research interests comprise active computer vision, object recognition and tracking, 3D reconstruction, and plenoptic modeling, as well as computer vision for autonomous systems. He is author and coauthor of over 80 journal papers and technical articles. He is member of the IEEE computer society, DAGM, and GI. For his work on object tracking, plenoptic modeling, and active object recognition and state estimation, he was awarded with the DAGM best paper awards in 1996, 1999, and 2001, respectively. Heinrich Niemann obtained the degree of Dipl.-Ing. in Electrical Engineering and Dr.-Ing. from Technical University Hannover, Germany. He worked at the Fraunhofer Institut fur Informationsverarbeitung in Technik und Biologie, Karlsruhe, and at Fachhochschule Giessen in the department of Electrical Engineering. Since 1975 he has been Professor of Computer Science at the University of Erlangen-Nurnberg, where he was dean of the engineering faculty of the university from 1979–1981. From 1988–2000 he was head of the research group Knowledge Processing at the Bavarian Research Institute for Knowledge-based Systems (FORWISS). Since 1998 he has been the speaker of a special research area entitled Model-based Analysis and Visualization of Complex Scenes and Sensor Data, which is funded by the German Research Foundation (DFG). His fields of research are speech and image understanding and the application of artificial intelligence techniques in these fields. He is on the editorial boards of Signal Processing, Pattern Recognition Letters, Pattern Recognition and Image Analysis, and Journal of Computing and Information Technology. He is the author or coauthor of 7 books and about 400 journal and conference contributions, as well as editor or coeditor of 24 volumes of proceedings and special issues. He is a member of DAGM, ISCA, EURASIP, GI, and IEEE, and a Fellow of IAPR.     

Scheduling algorithms based on weakly hard real-time constraints

The problem of scheduling weakly hard real-time tasks is addressed in this paper.The paper first analyzes the characters of μ-pattern and weakly hard real-time constraints,then,presents two scheduling algorithms,Meet Any Algorithm and Meet Row Algorithm,for weakly hard real-time systems.Different from traditional algorithms used to guarantee deadlines,MeetAny Algorithm and Meet Row Algorithm can guarantee both deadlines and constraints.Meet Any Algorithm and Meet Row Algorithm try to find out the probabilities of tasks breaking constraints and increase task‘s priority in advance,but not till the last moment.Simulation results show that these two algorithms are better than other scheduling algorithms dealing with constraints and can largely decrease worst-case computation time of real-time tasks.     

Finding centric local outliers in categorical/numerical spaces

Outlier detection techniques are widely used in many applications such as credit-card fraud detection, monitoring criminal activities in electronic commerce, etc. These applications attempt to identify outliers as noises, exceptions, or objects around the border. The existing density-based local outlier detection assigns the degree to which an object is an outlier in a numerical space. In this paper, we propose a novel mutual-reinforcement-based local outlier detection approach. Instead of detecting local outliers as noise, we attempt to identify local outliers in the center, where they are similar to some clusters of objects on one hand, and are unique on the other. Our technique can be used for bank investment to identify a unique body, similar to many good competitors, in which to invest. We attempt to detect local outliers in categorical, ordinal as well as numerical data. In categorical data, the challenge is that there are many similar but different ways to specify relationships among the data items. Our mutual-reinforcement-based approach is stable, with similar but different user-defined relationships. Our technique can reduce the burden for users to determine the relationships among data items, and find the explanations why the outliers are found. We conducted extensive experimental studies using real datasets. Jeffrey Xu Yu received his B.E., M.E. and Ph.D. in computer science, from the University of Tsukuba, Japan, in 1985, 1987 and 1990, respectively. Jeffrey Xu Yu was a research fellow in the Institute of Information Sciences and Electronics, University of Tsukuba (Apr. 1990–Mar. 1991), and held teaching positions in the Institute of Information Sciences and Electronics, University of Tsukuba (Apr. 1991–July 1992) and in the Department of Computer Science, Australian National University (July 1992–June 2000). Currently he is an Associate Professor in the Department of Systems Engineering and Engineering Management, Chinese University of Hong Kong. His major research interests include data mining, data stream mining/processing, XML query processing and optimization, data warehouse, on-line analytical processing, and design and implementation of database management systems. Weining Qian is currently an assistant professor of computer science at Fudan University, Shanghai, China. He received his M.S. and Ph.D. degrees in computer science from Fudan University in 2001 and 2004, respectively. He was supported by a Microsoft Research Fellowship when he was doing the research presented in this paper, and he is supported by the Shanghai Rising Star Program. His research interests include data mining for very large databases, data stream query processing and mining and peer-to-peer computing. Hongjun Lu received his B.Sc. from Tsinghua University, China, and M.Sc. and Ph.D. from the Department of Computer Science, University of Wisconsin–Madison. He worked as an engineer in the Chinese Academy of Space Technology, and a principal research scientist in the Computer Science Center of Honeywell Inc., Minnesota, USA (1985–1987), and a professor at the School of Computing of the National University of Singapore (1987–2000), and is a full professor of the Hong Kong University of Science and Technology. His research interests are in data/knowledge-base management systems with an emphasis on query processing and optimization, physical database design, and database performance. Hongjun Lu is currently a trustee of the VLDB Endowment, an associate editor of the IEEE Transactions on Knowledge and Data Engineering (TKDE), and a member of the review board of the Journal of Database Management. He served as a member of the ACM SIGMOD Advisory Board in 1998–2002. Aoying Zhou born in 1965, is currently a professor of computer science at Fudan University, Shanghai, China. He won his Bachelor degree and Master degree in Computer Science from Sichuan University in Chengdu, Sichuan, China in 1985 and 1988. respectively, and a Ph.D. degree from Fudan University in 1993. He has served as a member or chair of the program committees for many international conferences such as VLDB, ER, DASFAA, WAIM, and etc. His papers have been published in ACM SIGMOD, VLDB, ICDE and some international journals. His research interests include data mining and knowledge discovery, XML data management, web query and searching, data stream analysis and processing and peer-to-peer computing.     

BCL—3：Aigh Performance Basic Communication Protocol for Commodity Superserver DAWNING—3000

This paper introduces the design and implemetation of BCL-3,a high performance low-level communication software running on a cluster of SMPs(CLUMPS) called DAWNING-3000,BCL-3 provides flexible and sufficient functionality to fulfill the communication requirements of fundamental system software developed for DAWNING-3000 while guaranteeing security,scalability,and reliability,Important features of BCL-3 are presented in the paper,including special support for SMP and heterogeneous network environment,semiuser-level communication,reliable and ordered data transfer and scalable flow control,The performance evaluation of BCL-3 over Myrinet is also given.     

<Emphasis Type="Italic">LFTOP</Emphasis>: An <Emphasis Type="Italic">LF</Emphasis>-Based Approach to Domain-Specific Reasoning

A new approach to domain-specific reasoning is presented that is based on a type-theoretic logical framework(LF) but does not require the user to be an expert in type theory. The concepts of the domain and its related reasoning systems are formalized in LF, but the user works with the system through a syntax and interface appropriate to his/her work. A middle layer provides translation between the user syntax and LF, and allows additional support for reasoning(e.g., model checking). Thus, the complexity of the logical framework is hidden but the benefits of using type theory and its related tools are retained, such as precision and machine-checkable proofs. This approach is investigated through a number of case studies: here, the authors consider the verification of properties of concurrency. The authors have formalized a specification language (CCS) and logic (μ-calculus) in LF, together with useful lemmas, and a user-oriented syntax has been designed. The authors demonstrate the approach with simple examples. However, applying lemmas to objects introduced by the user may result in framework-level objects which cannot be translated back to the user level. The authors discuss this problem, define a notion of adequacy, and prove that in this case study, translation can always be reversed.     

The faster higher-order cellular automaton for hyper-parallel undistorted data compression

This paper defines second-order and third-order permutation global functions and presents the corresponding higher-order cellular automaton approach to the hyper-parallel undistorted data compression.The genetic algorithm is successfully devoted to finding out all the correct local compression rules for the higher-order cellualr automaton.The correctness of the higher-order compression rules,the time complexity,and the systolic hardware implementation issue are discussed.In comparison with the first-order automation method reported,the proposed higher-order approach has much faster compression speed with almost the same degree of cellular structure complexity for hardware implementation.