Search

Information modelling is a collection of dynamic processes, in which its content develops from physical processes to abstract knowledge structures. We study that collection on several levels of abstraction of human cognition and knowledge. These processes can be performed through various approaches, on several levels, and by using several perspectives. We concentrate on active conceptual modelling, which has become important in the science and technology, including educational sciences and learning. It is a process of recognition, finding or creating relevant concepts and conceptual models which describe the UoD, representing the conceptual content of information to be contained in the IS. This characterisation contains the construction of new concepts, too. We study methods for collecting information from various sources in the UoD and accumulating it as possibly actual instances of various types of pre-defined concepts. Some of these instances may be cases of sudden events or processes. They should be recognised as concepts and included in to the conceptual schema. To some extent, some concepts may be constructed which fit to this collected information. During the adaptation process we are applying active conceptual modelling for learning, which organises our conceptual schema in a new way. Learning is a process in which a learner re-organises, removes or refills his knowledge structures by applying his newly organised conceptual schema. [ABSTRACT FROM AUTHOR]

The SPAWAR Systems Center (SSC San Diego) of the U.S. Navy hosted two workshops on Active Conceptual Modeling of Learning (ACM-L). The first workshop was held at SSC San Diego on May 10-12, 2006 to introduce the Science &Technology (S&T) Initiative and identify a Research and Development agenda for the technology development investigation. Eleven invited researchers in Conceptual Modeling presented position papers on the proposed S&T Initiative. The second workshop was held on November 8, 2006 at the 25th International Conference on Conceptual Modeling, ER 2006, 6-9 November 2006, in Tucson, Arizona. Complementary to the May Workshop, the November workshop was a forum for the international researchers and practitioners to present their papers as a result of a call for papers and to exchange ideas from various perspectives of the subject. This paper describes research issues identified by participants from the two ACM-L workshops. [ABSTRACT FROM AUTHOR]

Metaphor is a high-level abstract concept that can be an important part of active conceptual modeling. In this paper, we use the extended Unified Modeling Language (UML) for metaphor modeling. We discuss how to create UML diagrams to capture knowledge about metaphors. The metaphor-based processing system on the Semantic Web can support new query/search operations. Such a computer system can be used for a broad spectrum of applications such as predicting surprises (e.g., terrorist attacks) or generating automatically new innovations. [ABSTRACT FROM AUTHOR]

There are four classes of information system that are not well served by current modelling techniques. First, there are systems for which the number of instances for each entity is relatively low resulting in data definition taking a disproportionate amount of effort. Second, there are systems where the storage of data and the retrieval of information must take priority over the full definition of a schema describing that data. Third, there are those that undergo regular structural change and are thus subject to information loss as a result of changes to the schema's information capacity. Finally, there are those systems where the structure of the information is only partially known or for which there are multiple, perhaps contradictory, competing hypotheses as to the underlying structure. This paper presents the Low Instance-to-Entity Ratio (LItER) Model, which attempts to circumvent some of the problems encountered by these types of application. The two-part LItER modelling process possesses an overarching architecture which provides hypothesis, knowledge base and ontology support together with a common conceptual schema. This allows data to be stored immediately and for a more refined conceptual schema to be developed later. It also facilitates later translation to EER, ORM and UML models and the use of (a form of) SQL. Moreover, an additional benefit of the model is that it provides a partial solution to a number of outstanding issues in current conceptual modelling systems. [ABSTRACT FROM AUTHOR]

Worldwide globalization increases the complexity of problem solving and decision-making, whatever the endeavor is. This calls for a more accurate and complete understanding of underlying data, processes and events. Data representations have to be as accurate as possible, spanning from the current status of affairs to its past and future statuses, so that it becomes feasible, in particular, to elaborate strategies for the future based on an analysis of past events. Active conceptual modeling is a new framework intended to describe all aspects of a domain. It expands the traditional modeling scope to include, among others, the ability to memorize and use knowledge about the spatial and temporal context of the phenomena of interest, as well as the ability to analyze the same elements under different perspectives. In this paper we show how these advanced modeling features are provided by the MADS conceptual model. [ABSTRACT FROM AUTHOR]

Conceptual changes and historical information have not been emphasized in traditional approaches to conceptual modeling such as the entity-relationship approach. Effective representations for such changes are needed to support robust machine learning and computer-aided organizational learning. However, these aspects have been modeled and studied in other contexts, such as software maintenance, version control, software transformations, etc. This paper reviews some relevant previous results, shows how they have been used to simplify conceptual models to help people make sense out of complex changing situations, and suggests some connections to conceptual models of machine learning. Areas where research is required to support conceptual models for adaptive systems are also explored. These are suggested by studies of the issues surrounding deployment of adaptive systems in mission critical environments. [ABSTRACT FROM AUTHOR]

This paper presents a context-aware text summarizer based on ontologies intended to be used for adapting information to mobile devices. The system generates summaries from texts according to the profile of the user and the context where he/she is at the moment. Context is determined by spatial and temporal localization. Ontologies are used to allow identifying which parts of the texts are related to the user's profile and to the context. Ontologies are structured as hierarchies of concepts and concepts are represented by keywords with a weight associated. [ABSTRACT FROM AUTHOR]

We argue that a key requirement on an information system that can implement an active conceptual model of learning from surprises is the ability to query data that is not query-able by content, especially data streams;we suggest that such data be queried by context. We propose an enhancement of entity-relationship modeling with active constructs in order to permit such streams to have context-based relationships with standard data. We propose a framework wherein the analysis of surprises and the subsequent monitoring of states that are ripe for such events are possible by the use of such contexts. [ABSTRACT FROM AUTHOR]

Reducing the complexity and surprise of emergencies can efficiently alleviate negative impacts on society, either local or global. A good model which can simplify complex events by constructing views to describe changes of entity behaviors and the dynamic and time-varying relationships is the key approach to handle surprise crises. Conventional conceptual modeling has limitations on mapping dynamic real world. Active modeling is suggested as the appropriate way to deal with such surprises. A case study of Hurricane Katrina is used as an example to explain some active modeling concepts including temporal conceptual modeling, multi-perspective modeling, and data, information and knowledge integration. [ABSTRACT FROM AUTHOR]

Terrorist organizations attain their goals by attacking various targets to jeopardize human lives and intimidate governments. As new terrorist attacks almost always aim to break the mold of old plots, tracing the dynamic behaviors of terrorists becomes crucial to national defense. This paper proposes using active modeling in analyzing unconventional attacks in the design of counterterrorism system. The intelligent terrorism detection system not only detects potential threats by monitoring terrorist networks with identified threat patterns, but also continually integrates new threat features in terrorist behaviors and the varying relationships among terrorists. [ABSTRACT FROM AUTHOR]

The new field of active conceptual modeling for learning from surprises (ACM-L) may be helpful in preserving life, protecting property, and improving quality of life. The conceptual modeling community has developed sound theory and practices for conceptual modeling that, if properly applied, could help analysts model and predict more accurately. In particular, we need to associate more semantics with links, and we need fully reified high-level objects and relationships that have a clear, formal underlying semantics that follows a natural, ontological approach. We also need to capture more dynamic aspects in our conceptual models to more accurately model complex, dynamic systems. These concepts already exist, and the theory is well developed; what remains is to link them with the ideas needed to predict system evolution, thus enabling risk assessment and response planning. No single researcher or research group will be able to achieve this ambitious vision alone. As a starting point, we recommend that the nascent ACM-L community agree on a common core model that supports all aspects—static and dynamic—needed for active conceptual modeling in support of learning from surprises. A common core will more likely gain the traction needed to sustain the extended ACM-L research effort that will yield the advertised benefits of learning from surprises. [ABSTRACT FROM AUTHOR]

Run-time application environments are affected by the changes in mini-world or technology changes. Large number of applications are process driven. For robust applications that can evolve over time, there is a need for a methodology that implicitly handles changes at various levels from mini-world to run-time environment through a layers of models and systems. In this paper, we present ER* methodology for evolving applications. In the context of this paper, the role of two-way active behaviour and template driven development of applications is presented. This methodology facilitates capturing active behaviour from run-time transactions and provides a means of using this knowledge to guide subsequent application design and its evolution. [ABSTRACT FROM AUTHOR]

Database and information systems technology has substantially changed. Nowadays, content management systems, (information-intensive) web services, collaborating systems, internet databases, OLAP databases etc. have become buzzwords. At the same time, object-relational technology has gained the maturity for being widely applied. Conceptual modelling has not (yet) covered all these novel topics. It has been concentrated for more than two decades around specification of structures. Meanwhile, functionality, interactivity and distribution must be included into conceptual modelling of information systems. Also, some of the open problems that have been already discussed in 1987 [15, 16] still remain to be open. At the same time, novel models such as object-relational models or XML-based models have been developed. They did not overcome all the problems but have been sharpening and extending the variety of open problems. The open problem presented are given for classical areas of database research, i.e., structuring and functionality. The entire are of distribution and interaction is currently an area of very intensive research. The presentation of open problems is combined with the introduction to the achievements of conceptual modelling. The paper develops an approach to conceptual modelling for object-relational, collaborating information systems that support virtual communities of work, integration of information systems, varieties of architecture such as the OLTP-OLAP architecture, varieties of play-out and play-in systems, and data analysis engines. The paper is based on an extended entity-relationship model that covers all structuring facilities of object-relational systems. It uses the theory of media types and storyboards for the specification of interactivity and provides a framework for collaboration. The paper presents 20 open problems that need to be solved for conceptual modelling. The problems are sketched. Main references and the background are given. Additional references can be provided by the author on demand. [ABSTRACT FROM AUTHOR]

One distinct characteristics of the context-aware systems is their ability to react and adapt to the evolution of the environment, which is often a result of changes in the values of various (possibly correlated) attributes. Based on these changes, reactive systems typically take corrective actions, e.g., adjusting parameters in order to maintain the desired specifications of the system's state. Pro-active systems, on the other hand, may change the mode of interaction with the environment as well as the desired goals of the system. In this paper we describe our (ECA)2 paradigm for reactive behavior with proactive impact and we present our ongoing work and vision for a system that is capable of context-aware adaptation, while ensuring the maintenance of a set of desired behavioral policies. Our main focus is on developing a formalism that provides tools for expressing normal, as well as defeasible and/or exceptional specification. However, at the same time, we insist on a sound semantics and the capability of answering hypothetical "what-if" queries. Towards this end, we introduce the high-level language $\mathcal L_{\mathcal EAR}$ that can be used to describe the dynamics of the problem domain, specify triggers under the (ECA)2 paradigm, and reason about the consequences of the possible evolutions. [ABSTRACT FROM AUTHOR]

Data Provenance refers to the lineage of data including its origin, key events that occur over the course of its lifecycle, and other details associated with data creation, processing, and archiving. We believe that tracking provenance enables users to share, discover, and reuse the data, thus streamlining collaborative activities, reducing the possibility of repeating dead ends, and facilitating learning. It also provides a mechanism to transition from static to active conceptual modeling. The primary goal of our research is to investigate the semantics or meaning of data provenance. We describe the W7 model that represents different components of provenance and their relationships to each other. We conceptualize provenance as a combination of seven interconnected elements including "what", "when", "where", "how", "who", "which" and "why". Each of these components may be used to track events that affect data during its lifetime. A homeland security example illustrates how current conceptual models can be extended to embed provenance. [ABSTRACT FROM AUTHOR]

This is a summary of the papers presented at the Active Conceptual Modeling of Learning (ACM-L) Workshop, November 8, 2006, Tucson, Arizona, USA, and several invited papers. [ABSTRACT FROM AUTHOR]

The concept of Active Conceptual Modeling of Learning (ACM-L) has been explored in order to capture content and context changes that permit a comprehensive learning from the past, understanding the present, and forecasting the future. Such capability has not been fully explored and it is not available with today's static oriented database system. The potential of creating a "database of intention" that can have its own aim to understand the intentions of its users and the changes to their environment. This paper explores an architectural approach for the "database of intention" with predictability power. The proposed architecture is presented, illustrated, and discussed. [ABSTRACT FROM AUTHOR]

Growing need for information retrieval, information processing, and the associated need for navigation in existing information spaces resulted in several approaches that aim to improve efficiency of the respective user tasks. However, problems related to user navigation and orientation in large open information spaces still persist possibly due to increasing demands and the imperfections of individual approaches. We propose an integrated search and navigation solution that takes advantage of the faceted browsing paradigm and visual navigation in graphs both extended with support for automatic personalization based on user context also taking advantage of a user's social network. The proposed solution is primarily evaluated in the domain of scientific publications, i.e. digital libraries, with possible extensions to other application domains. [ABSTRACT FROM AUTHOR]

In this paper was proposed a method for the description of web pages using web patterns. We will explain what we mean by the term "web pattern". We will present a taxonomy web patterns and a description of some their types. In the description of web patterns we will focus on properties which are useful for automatic detection on web pages. As a result of the detection we get a description of a web page using found web patterns. The description can be used for reordering and clustering of a web page set. [ABSTRACT FROM AUTHOR]

Contemporary XML documents can be tens of megabytes long, and reducing their size, thus allowing to transfer them faster, poses a significant advantage for their users. In this paper, we describe a new XML compression scheme which outperforms the previous state-of-the-art algorithm, SCMPPM, by over 9% on average in compression ratio, having the practical feature of streamlined decompression and being almost twice faster in the decompression. Applying the scheme can significantly reduce transmission time/bandwidth usage for XML documents published on the Web. The proposed scheme is based on a semi-dynamic dictionary of the most frequent words in the document (both in the annotation and contents), automatic detection and compact encoding of numbers and specific patterns (like dates or IP addresses), and a back-end PPM coding variant tailored to efficiently handle long matching sequences. Moreover, we show that the compression ratio can be improved by additional 9% for the price of a significant slow-down. [ABSTRACT FROM AUTHOR]

The development of structure analysis that constitutes the core part of social network analysis is continuously supported by the rapid expansion of different kinds of social networks available in the Internet. The network analyzed in this paper is built based on the email communication between people. Exploiting the data about this communication some personal social features can be discovered, including personal position that means individual importance within the community. The evaluation of position of an individual is crucial for user ranking and extraction of key network members. The new method of personal importance analysis is presented in the paper. It takes into account the strength of relationships between network members, its dynamic as well as personal position of the nearest neighbours. The requirements for the commitment function that reflects the strength of the relationship are also specified. In order to validate the proposed method, the dataset containing Enron emails is utilized; first to build the virtual social network and afterwards to assess the position of the network members. [ABSTRACT FROM AUTHOR]

Over the last decade, Web and multimedia data have grown at a staggering rate. Users of new media now have great expectations of what they can see on the Web. In addition, most information retrieval systems, including Web search engines, use similarity ranking algorithms based on a vector space model to find relevant information in response to a user's request. However, the retrieved information is frequently irrelevant, because most of the current information systems employ index terms or other techniques that are variants of term frequency. This paper proposed a new approach, named "the dynamic multimedia presentations with a Generality Model," to offer a customized multi-modal presentation for an intended audience. Moreover, we proposed a new criterion, "generality," that provides an additional basis on which to rank retrieved documents. To support multi-modal presentation, our proposed story model created story structures that can be dynamically instantiated for different user requests from various multi-modal elements. The generality is a level of abstraction to retrieve results based on desired generality appropriate for a user's knowledge and interests. We compared traditional web news search functions and our story model by using usability test. The result shows that our multimedia presentation methodology is significantly better than the current search functions. We also compared our generality quantification algorithm with human judges' weighting of values to show that the developed algorithm is significantly correlated. [ABSTRACT FROM AUTHOR]

XBW [10] is modular program for lossless compression that enables testing various combinations of algorithms. We obtained best results with XML parser creating dictionary of syllables or words combined with Burrows-Wheeler transform - hence the name XBW. The motivation for creating parser that handles non-valid XML and HTML files, has been system EGOTHOR [5] for full-text searching. On files of size approximately 20MB, formed by hundreds of web pages, we achieved twice the compression ratio of bzip2 while running only twice as long. For smaller files, XBW has very good results, compared with other programs, especially for languages with rich morphology such as Slovak or German. For any big textual files, our program has good balance of compression and run time. Program XBW enables use of parser and coder with any implemented algorithm for compression. We have implemented Burrows-Wheeler transform which together with MTF and RLE forms block compression, dictionary methods LZC and LZSS, and finally statistical method PPM. Coder offers choice of Huffman and arithmetic coding. [ABSTRACT FROM AUTHOR]

We have developed and implemented [1,2] infrastructure and RDF storage for the Semantic Web. When we filled it with data the need for some tool that could explore the data became evident. Unfortunately, none of existing solutions fulfills requirements imposed by the data and users expectations. This paper presents our RDF visualizer that was designed specifically to handle large RDF data by means of incremental navigation. A detailed description of the algorithm is given as well as actual results produced by the visualizer. [ABSTRACT FROM AUTHOR]

In this paper we describe the process of experimental ontology data set creation. Such a semantically enhanced data set is needed in experimental evaluation of applications for the Semantic Web. Our research focuses on various levels of the process of data set creation - data acquisition using wrappers, data preprocessing on the ontology instance level and adjustment of the ontology according to the nature of the evaluation step. Web application aimed at clustering of ontology instances is utilized in the process of experimental evaluation, serving both as an example of an application and visual presentation of the experimental data set to the user. [ABSTRACT FROM AUTHOR]

The need for data privacy motivates the development of new methods that allow to protect data minimizing the disclosure risk without losing valuable statistical information. In this paper, we propose a new protection method for numerical data called Ordered Neural Networks (ONN). ONN presents a new way to protect data based on the use of Artificial Neural Networks (ANNs). The main contribution of ONN is a new strategy for preprocessing data so that the ANNs are not capable of accurately learning the original data set. Using the results obtained by the ANNs, ONN generates a new data set similar to the original one without disclosing the real sensible values. We compare our method to the best methods presented in the literature, using data provided by the US Census Bureau. Our experiments show that ONN outperforms the previous methods proposed in the literature, proving that the use of ANNs is convenient to protect the data efficiently without losing the statistical properties of the set. [ABSTRACT FROM AUTHOR]

In this paper we present a communicational proof-of-work - a new tool that can be used, among others, for filtering messages and limiting spam. Our idea can be regarded as an analogue of regular proofs-of-work introduced by Dwork and Naor. The idea presented in our paper is as follows: the prover has to provide a convincing evidence that he had communicated with other, randomly chosen entity. This approach is essentially different from previous proofs-of-work, because fulfilling this requirement does not depend on resources owned by the prover (e.g. sender) only. Thanks to this, even if the adversary (e.g. spammer) has an access to much more efficient computers, he does not have any important advantage over regular, honest users of the system. We also demonstrate some other applications of the presented idea as well as some extensions based on its combination with regular proofs-of-work. Together with algorithms we also briefly describe a proof of our concept i.e. working implementation. We present some experimental data and statistics obtained during tests of our application. [ABSTRACT FROM AUTHOR]

Much research work has recently focused on the problem of representing historical information in XML. In this paper, we describe an ongoing work to represent XML changes. Our model is a three-dimensional XML-based model (3D_XML in short) for representing and querying histories of XML documents. The proposed model incorporates three time dimensions, valid time, transaction time, and efficacy time without extending the syntax of XML. We use XQuery to express complex temporal queries on the evolution of the document contents. We believe that native XML databases (NXDs) present a viable alternative to relational temporal databases when complex time dependent data has to be manipulated and stored. So NXDs will be our choice. [ABSTRACT FROM AUTHOR]

We present an algorithm for intelligent prediction of user requests in a system based on the services hosted by independent providers. Data extracted from requests is organized in a dynamically changing graph representing dependencies between operations and input arguments as well as between groups of arguments mutually coexisting in requests. The purpose of the system is to suggest the possible set of future requests basing on the last submitted request and the state of the graph. Additionally the response time may be shortened owing to the background executing and caching of the requests most likely to be asked. The knowledge extracted from the graph analysis reveals the mechanisms that govern the sequences of invoked requests. Such knowledge can help in semi-automatic generation of business processes. The algorithm is a part of ASK-IT (Ambient Intelligence System of Agents for Knowledge-based and Integrated Services for Mobility Impaired users) EU project. [ABSTRACT FROM AUTHOR]

This paper proposes a new hybrid method to formally verify whether the security specification of a target information system satisfies security functional requirements defined in ISO/IEC 15408 evaluation criteria for security. We classify at first the security functional requirements of ISO/IEC 15408 into two classes: static requirements concerning static properties and dynamic requirements concerning dynamic behavior of target systems, and then formalize the static requirements with Z notation and the dynamic requirements with temporal logic. Thus, we can verify static properties using theorem-proving and dynamic behavior using model-checking. As a result, developers can easily use the method to verify whether the security specification of a target information system satisfies both static and dynamic security functional requirements defined in ISO/IEC 15408. The new method is an evolution and improvement of our early verification method where only Z notation was adapted and to verify dynamic behavior of target systems is difficult. [ABSTRACT FROM AUTHOR]

We consider the following problem: users of an organization wish to outsource the storage of sensitive data to a large database server. It is assumed that the server storing the data is untrusted so the data stored have to be encrypted. We further suppose that the manager of the organization has the right to access all data, but a member of the organization can not access any data alone. The member must collaborate with other members to search for the desired data. In this paper, we investigate the notion of threshold privacy preserving keyword search (TPPKS) and define its security requirements. We construct a TPPKS scheme and show the proof of security under the assumptions of intractability of discrete logarithm, decisional Diffie-Hellman and computational Diffie-Hellman problems. [ABSTRACT FROM AUTHOR]

This article presents additional necessary measures that enable us to use Pict as an object-capability programing language. It is desirable to be able to assess the worst possible threat that we—users—risk if we run a given program. If we know the threat, we are able to decide whether or not we are willing to risk running the program. The cost of a security audit that reveals such an assessment will be non-zero but it need not to be directly dependent on the size of the whole original program. It is possible to write programs in such a way that this analysis can be reliably performed on a fraction of the original program—on the trusted computing base. This technique does not always give the most accurate assessment but it gives sound and interesting assessment relatively cheaply. It does not prevent usage of other techniques that can further refine the initial assessment. [ABSTRACT FROM AUTHOR]

Based on the principle that "the ultimate method to secure a network is to disconnect it", the Lock-Keeper technology has been known as an efficient approach to guarantee the high-level security and prevent online network attacks by physically separating the protected hosts or networks. Because of its simple idea and extensible architecture, the Lock-Keeper system can be easily and seamlessly integrated with other security methods or solutions to provide thorough protection for most actual network-based applications. This paper will propose an advanced strong authentication framework based on the Lock-Keeper. Thanks to Lock-Keeper's physical disconnection, all the credentials, privacies and policies required by the authentication mechanism can be securely stored and manipulated by being completely isolated with both the external and the internal networks. The whole authentication procedure can be performed in the clean and trusted Lock-Keeper GATE component. Based on the proposed framework, a prototypical platform is implemented in the Lock-Keeper to enhance the security of the Lock-Keeper Web Service module, which is one of important Lock-Keeper application modules, and can be applied to secure most web applications in Service-Oriented-Architecture environment. [ABSTRACT FROM AUTHOR]

We analyze the Threeballot voting system proposed recently by R. Rivest. We investigate the relation between the number of the candidates in a race and effectiveness of Strauss' attack. We also show that in a reasonable scenario it is impossible to reconstruct voters' preferences for a single race with two candidates. [ABSTRACT FROM AUTHOR]

A party using encrypted communication or storing data in an encrypted form might be forced to show the corresponding plaintext. It may happen for law enforcement reasons as well as for evil purposes. Deniable encryption scheme introduced by Canetti et al. shows that cryptography can be used against revealing information: the owner of the data may decrypt it in an alternative way to a harmless plaintext. Moreover, it is impossible to check if there is another hidden plaintext. The scheme of Canetti is inefficient in the sense that it is a special purpose scheme and using it indicates that there is some hidden message inside. We show that deniable encryption can be implemented in a different way so that it does not point to exploiting deniable encryption. Moreover, it is quite straightforward, so it can be used for both good and evil purposes. Apart from that we show that even the special purpose original scheme can be extended to allow, in some circumstances, any "depth" of deniability. [ABSTRACT FROM AUTHOR]

This article describes the way how some amount of information can be stored into DNS, particularly in the cache of DNS server. Then it can be retrieved back, possibly by another host in the network. Based on this principle we can construct a communication channel, hidden in the usual traffic, or a memory medium. Considering this kind of media, some basic characteristics and limits, like capacity, transfer speed, error rate, persistence of information, etc., are discussed here. Simple algorithm deciding whether a bit in the memory has been set or not was proposed and implemented. Its performance and optimal setting was examined. The results show that under some circumstances error rates about 0.003, when retrieving the information, can be achieved. [ABSTRACT FROM AUTHOR]

A metaheuristic for solving complex problems is proposed. The introduced Sensitive Robot Metaheuristic (SRM) is based on the Ant Colony System optimization technique. The new model relies on the reaction of virtual sensitive robots to different stigmergic variables. Each robot is endowed with a particular stigmergic sensitivity level ensuring a good balance between search diversification and intensification. Comparative tests are performed on large-scale NP-hard robotic travel problems. These tests illustrate the effectiveness and robustness of the proposed metaheuristic. [ABSTRACT FROM AUTHOR]

In the paper, a new memetic algorithm for decision tree learning is presented. The proposed approach consists in extending an existing evolutionary approach for global induction of classification trees. In contrast to the standard top-down methods, it searches for the optimal univariate tree by evolving a population of trees. Specialized genetic operators are selectively applied to modify both tree structures and tests in non-terminal nodes. Additionally, a local greedy search operator is embedded into the algorithm, which focusses and speeds up the evolutionary induction. The problem of over-fitting is mitigated by suitably defined fitness function. The proposed method is experimentally validated and preliminary results show that the proposed approach is able to effectively induce accurate and concise decision trees. [ABSTRACT FROM AUTHOR]

Model complexity of feedforward neural networks is studied in terms of rates of variable-basis approximation. Sets of functions, for which the errors in approximation by neural networks with n hidden units converge to zero geometrically fast with increasing number n, are described. However, the geometric speed of convergence depends on parameters, which are specific for each function to be approximated. The results are illustrated by examples of estimates of such parameters for functions in infinite-dimensional Hilbert spaces. [ABSTRACT FROM AUTHOR]

For a continuous-time quantum walk on a line the variance of the position observable grows quadratically in time, whereas, for its classical counterpart on the same graph, it exhibits a linear, diffusive, behaviour. A quantum walk, thus, propagates at a rate which is linear in time, as compared to the square root rate for a classical random walk. Indeed, it has been suggested that there are graphs that can be traversed by a quantum walker exponentially faster than by the classical random analogue. In this note we adopt the approach of exploring the conditions to impose on a Markov process in order to emulate its quantum counterpart: the central issue that emerges is the problem of taking into account, in the numerical generation of each sample path, the causative effect of the ensemble of trajectories to which it belongs. How to deal numerically with this problem is shown in a paradigmatic example. [ABSTRACT FROM AUTHOR]

We present quantum query and time complexity bounds for group testing problems. For a set S and a binary operation on S, we consider the decision problem whether a groupoid, semigroup or quasigroup is a group. Our quantum algorithms for these problems improve the best known classical complexity bounds. We also present upper and lower bounds for testing associativity, distributivity and commutativity. [ABSTRACT FROM AUTHOR]

We introduce the notion of net-slice to describe a subnet of a marked Petri net Σ that approximates Σ's temporal behaviour with respect to a set of places P. We consider slices Σ′ whose set of places comprises the places referred to by a CTL* formula φ. If Σ is fair w.r.t. the transitions of a slice, Σ ⊧ φ can be verified and falsified by examining the slice, given φ is a CTL* formula built without using the next-time operator. Verification of LTL$_{\textrm{-\tiny{X}}}$ formulas is thus possible under these very weak fairness assumptions, though LTL formulas using next-time can be falsified. [ABSTRACT FROM AUTHOR]

In John Tantalo's on-line game Planarity the player is given a non-plane straight-line drawing of a planar graph. The aim is to make the drawing plane as quickly as possible by moving vertices. Pach and Tardos have posed a related problem: can any straight-line drawing of any planar graph with n vertices be made plane by vertex moves while keeping ${\Omega(n^\ensuremath{\varepsilon})}$ vertices fixed for some absolute constant $\ensuremath{\varepsilon} >0$? It is known that three vertices can always be kept (if n ≥ 5). We still do not solve the problem of Pach and Tardos, but we report some progress. We prove that the number of vertices that can be kept actually grows with the size of the graph. More specifically, we give a lower bound of $\Omega(\sqrt{\log n / \log \log n})$ on this number. By the same technique we show that in the case of outerplanar graphs we can keep a lot more, namely $\Omega(\sqrt{n})$ vertices. We also construct a family of outerplanar graphs for which this bound is asymptotically tight. [ABSTRACT FROM AUTHOR]

This paper presents a parallel artificial immune system designed for graph coloring. The algorithm is based on the clonal selection principle. Each processor operates on its own pool of antibodies and a migration mechanism is used to allow processors to exchange information. Experimental results show that migration improves the performance of the algorithm. The experiments were performed using a high performance cluster on a set of well-established graph instances available on the Web. [ABSTRACT FROM AUTHOR]

taDOM* protocols are designed to provide lock-based approach to handle multiple access to XML databases. The notion of taDOM+ protocol is formalized and generalized and a formal model of taDOM+ lock manager that is parameterized in the number of transactions and in the size of database is represented. An important class of safety properties of taDOM+ lock managers were proven to be checked by examining just a small number of finite-state instances of the parameterized model. Our results were applied to prove a generalized mutual exclusion property, known as repeatable-read, of taDOM2+ and taDOM3+ lock managers by model-checking. [ABSTRACT FROM AUTHOR]

We study some properties of quantum walks on the plane. First, we discuss the behavior of quantum walks when moving marked locations are introduced. Second, we present an exceptional case, when quantum walk fails to find any of the marked locations. [ABSTRACT FROM AUTHOR]

We investigate rational relations over trees. Our starting point is the definition of rational tree relations via rational expressions by Raoult (Bull. Belg. Math. Soc. 1997). We develop a new class of automata, called asynchronous tree automata, which recognize exactly these relations. The automata theoretic approach is convenient for the solution of algorithmic problems (like the emptiness problem). The second contribution of this paper is a new subclass of the rational tree relations, called separate-rational tree relations, defined via a natural restriction on asynchronous tree automata. These relations are closed under composition, preserve regular tree languages, and generate precisely the regular sets in the unary case (all these properties fail for the general model), and they are still more powerful than, for instance, the automatic tree relations. [ABSTRACT FROM AUTHOR]

We introduce the generalized notion of automata synchronization, so called partial synchronization, which holds for automata with partial transition function. We give a lower bound for the length of minimal synchronizing words for partial synchronizing automata. The difference, in comparison to the 'classical' synchronization, lies in the initial conditions: let $\mathcal{A}=(Q, A, \delta)$ be an automaton representing the dynamics of a particular system. In case of partial synchronization we assume that initial conditions (initial state of the system) can be represented by some particular states, that is by some P ⊂ Q, not necessarily by all possible states from Q. At first glance the above assumption limits our room for manoeuvre for constructing possibly long minimal synchronizing words (because of the lower number of states at the beginning). Unexpectedly this assumption allows us to construct longer minimal synchronizing words than in a standard case. In our proof we use Sperner's Theorem and some basic combinatorics. [ABSTRACT FROM AUTHOR]

We investigate the following problem: Given a list of n items and a function defined over lists of these items, generate a bounded amount of auxiliary information such that range queries asking for the value of the function on sub-lists can be answered within a certain time bound. For the function "mode" we improve the previously known time bound O(nεlogn) to O(nε) with space O(n2 − 2ε), where 0 ≤ ε< 1/2. We improve the space bound O(n2loglogn/logn) for an O(1) time bounded solution to O(n2/logn). For the function "median" the space bound O(n2loglogn/logn) is improved to O(n2log(k)n/logn) for an O(1) time solution, where k is an arbitrary constant and log(k) is the iterated logarithm. [ABSTRACT FROM AUTHOR]

We investigate off-line Turing machines equipped with a two-way input-tape and one work-tape. It is shown that the Element Distinctness Problem (EDP) for m binary strings of length ℓ = O(m/log2m) can be solved in time O(m3/2ℓ1/2) and space O(m1/2ℓ1/2) on a nondeterministic machine. This is faster than the best sorting algorithm on the computational model and optimal if time and space are considered simultaneously. For deterministic machines we give an optimal algorithm that can sort m binary strings consisting of ℓ bits each in O(m3/2ℓ) steps, provided that ℓ = O(m1/4). By modifying the solution we obtain the time bound O(m3/2ℓ) and the space bound O(m1/2ℓ2) for the EDP. [ABSTRACT FROM AUTHOR]