The G12 project recently started by National ICT Australia (NICTA)is an ambitious project to develop a software platform for solving large scale industrial combinatorial optimisation problems. The core design involves three languages: Zinc, Cadmium and Mercury (Group 12 of the periodic table). Zinc is a declarative modelling language for expressing problems, independent of any solving methodology. Cadmium is a mapping language for mapping Zinc models to underlying solvers and/or search strategies, including hybrid approaches. Finally, existing Mercury will be extended as a language for building extensible and hybridizable solvers. The same Zinc model, used with different Cadmium mappings, will allow us to experiment with different complete, local, or hybrid search approaches for the same problem. This talk will explain the G12 global design, the final G12 objectives, and our progress so far.

Amongst several fundamental aspects in multi-agent systems design, the definition of the agent interaction space is of the utmost importance. The specification of the agent interaction has several facets: syntax, semantics, and compliance verification.

In an open society, heterogenous agents can participate without showing any credentials. Accessing their internals or their knowledge bases is typically impossible, thus it is impossible to prove a priori that agents will indeed behave according to the society rules.

Within the SOCS (Societies Of ComputeeS) project, a language based on abductive semantics has been proposed as a mean to define interactions in open societies. The proposed language allows the designer to define open, extensible and not over-constrained protocols. Beside the definition language, a software tool has been developed with the purpose of verifying at execution time if the agents behave correctly with respect to the defined protocols.

This paper provides a tutorial overview of the theory and of the tools the SOCS project provided to design, define and test agent interaction protocols.

In first part of this course [28] we have laid the theoretical foundations for logic program specialisation, notably introducing the technique of partial deduction along with some basic techniques to automatically control it. In this part of the course we first present in Section 2 an advanced way of controlling polyvariance based upon characteristic trees. We then show in Section 3 how partial deduction can be extended into conjunctive partial deduction, incorporating much of the power of unfold/fold program transformation techniques, such as tupling and deforestation, while keeping the automatic control of partial deduction. Finally, in Section 4 we elaborate on combining abstract interpretation with conjunctive partial deduction, showing how together they are more powerful than either method alone.

Constraint Logic Programming (CLP) is one of the most successful branches of Logic Programming; it attracts the interest of theoreticians and practitioners, and it is currently used in many commercial applications. Since the original proposal, it has developed enormously: many languages and systems are now available either as open source programs or as commercial systems.

Also, CLP has been one of the technologies able to recruit researchers from other communities to the declarative programming cause. Current CLP engines include technologies and results developed in other communities, which themselves discovered logic as an invaluable tool to model and solve real-life problems.

Recently, partial deduction of logic programs has been extended to conceptually embed folding. To this end, partial deductions are no longer computed of single atoms, but rather of entire conjunctions; Hence the term “conjunctive partial deduction”.

Conjunctive partial deduction aims at achieving unfold/fold-like program transformations such as tupling and deforestation within fully automated partial deduction. However, its merits greatly surpass that limited context: Also other major efficiency gains can be obtained through considerably improved side-ways information propagation.

In this paper, we present a first investigation of conjunctive partial deduction in practice. We describe the concrete options used in the implementation(s), look at abstraction in a practical Prolog context, include and discuss an extensive set of benchmark results. ¿ From these, we can conclude that conjunctive partial deduction can indeed pay off in practice, beating its conventional precursor on a number of small to medium size programs. However, controlling it in a perfect way proves far from obvious, and a range of challenging open problems remain as topics for further research.

Recently there has been increased interest in logic programming- based default reasoning approaches which are not using negation-as failure in their object language. Instead, default reasoning is modelled by rules and a priority relation among them. Historically the first logic in this class was Defeasible Logic. In this paper we will study its relationship to other approaches which also rely on the idea of using logic rules and priorities. In particular we will study sceptical LPwNF, courteous logic programs, and priority logic.

Hierarchical Constraint Solving has been proposed as an adequate scheme to specify over-constrained problems where some of the constraints might remain unsatisfied. However it is often not clear which criteria should be adopted to select the “best” combination of constraints to be relaxed. In previous work we proposed IHCS — an Incremental Hierarchical Constraint Solver — but only with a single criterium. This paper presents IHCS as a general scheme to incrementally handle a hierarchy of constraints for a class of comparators using different criteria. The scheme is further extended with a satisfaction mode — given a threshold, this mode enables the search of “satisfactory” solutions to large problems whose optimization is not possible in acceptable time. This scheme can be integrated with different programming environments. In particular, we have integrated it with Prolog to produce an instance of an HCLP language. Because of its portability and incremental nature, IHCS is well suited for reactive systems, allowing the interactive introduction and removal of preferred constraints, illustrated in the examples presented in the paper.

Many real-life Constraint Satisfaction Problems are over constrained. In order to provide some kind of solution for such problems, this paper proposes a constraint relaxation mechanism fully integrated with the constraint solver. Such a constraint relaxation system must be able to perform two fundamental tasks: identification of constraints to relax and efficient constraint suppression. Assumption-based Truth Maintenance Systems propose a uniform framework to tackle those requirements. The main idea of our proposal is to use the ATMS to record and efficiently use all the information provided by the constraint solver while checking consistency. We detail the use of ATMS in our particular scheme and enlight their efficiency by comparing them with existing algorithms or systems (Menezes' IHCS and Bessière's DnAC4).

The G12 project recently started by National ICT Australia (NICTA) is an ambitious project to develop a software platform for solving large scale industrial combinatorial optimisation problems. The core design involves three languages: Zinc, Cadmium and Mercury (Group 12 of the periodic table). Zinc is a declarative modelling language for expressing problems, independent of any solving methodology. Cadmium is a mapping language for mapping Zinc models to underlying solvers and/or search strategies, including hybrid approaches. Finally, existing Mercury will be extended as a language for building extensible and hybridizable solvers. The same Zinc model, used with different Cadmium mappings, will allow us to experiment with different complete, local, or hybrid search approaches for the same problem. This talk will explain the G12 global design, the final G12 objectives, and our progress so far.

Temporal reasoning is an important task in many areas of computer science including planning, scheduling, temporal databases and instruction optimisation for compilers. Given a knowledge-base consisting of temporal relations, the main reasoning problem is to determine whether the knowledge-base is satisfiable, i.e., is there a scenario which is consistent with the information provided. However, many real world problems are over-constrained (i.e. unsatisfiable). To date, there has been little research aimed at solving over-constrained temporal reasoning problems. Recently, we developed standard backtracking algorithms to compute partial scenarios, in the spirit of Freuder and Wallace’s notion of partial satisfaction. While these algorithms were capable of obtaining optimal partial solutions, they were viable only for small problem sizes.

In this paper, we apply local search methods to overcome the deficiencies of the standard approach to solving over-constrained temporal reasoning problems. Inspired by our recent success in efficiently handling reasonably large satisfiable temporal reasoning problems using local search, we have developed two new local search algorithms using a random restart strategy and a TABU search. Further, we extend our previous constraint weighting algorithm to handle over-constrained problems. An empirical study of these new algorithms was performed using randomly generated under- and over-constrained temporal reasoning problems. We conclude that 1) local search significantly outperforms standard backtracking approaches on over-constrained temporal reasoning problems; and 2) the random restart strategy and TABU search have a superior performance to constraint weighting for the over-constrained problems. We also conjecture that the poorer performance of constraint weighting is due to distortions of non-zero global minima caused by the weighting process.

This paper describes a proxy signature scheme where a signer can delegate a partial signing right to a party who can then sign on behalf of the original signer to generate a partial proxy signature. A partial proxy signature can be converted into a full signature with the aid of the original signer. Our proxy signature scheme has the feature of deniability, i.e., only the designated receiver can verify the partial proxy signature and the full signature associated to him, while they are not transferable. This paper also describes an application of our scheme in a deniable optimistic fair exchange.

Biologically inspired design (BID) can be viewed as an example of analogy-based design. Existing models of analogy-based design do not fully account for the gen eration of complex solutions in BID, especially those which contain compound so lutions. In this paper we develop a conceptual framework of compound analogical designthat explains the generation of compound solutions in design through op portunistic interaction of two related processes: analogical transfer and problem decomposition. We apply this framework to analyze three sample biologically in spired designs that contain compound solutions.

A coupon represents the right to claim some service which is typically offered by vendors. In practice, issuing bundled multi-coupons is more efficient than issuing single coupons separately. The diversity of interests of the parties involved in a coupon system demands additional security properties beyond the common requirements (e.g., unforgeability). Customers wish to preserve their privacy when using the multi-coupon bundle and to prevent vendors from profiling. Vendors are interested in establishing a long-term customer relationship and not to subsidise one-time customers, since coupons are cheaper than the regular price. We propose a secure multi-coupon system that allows users to redeem a predefined number of single coupons from the same multi-coupon. The system provides unlinkability and also hides the number of remaining coupons of a multi-coupon from the vendor. A method used in the coupon system might be of independent interest. It proves knowledge of a signature on a message tuple of which a single message can be revealed while the remaining elements of the tuple, the index of the revealed message, as well as the signature remain hidden.

We investigate the optimization of extended relational queries used in systems holding, for example, spatial, multimedia or constraint data. For such queries we must account for the built-in relations specific to the kind of data, and application dependent relationships between different relations. We show that the constraint database perspective and the use of constrained tuple-generating dependencies provides a general framework in which to address semantic query optimization for these queries. We establish some sufficient conditions for query transformations involving the introduction of relations, extending work in the literature for conventional databases. We introduce semantic query partition (SQP) as a useful technique for optimizing queries with expensive operations, and investigate the problem of generating subqueries, which is central to the use of SQP.

Abstract

Unlike today where the majority of diagrams are static, lifeless objects reflecting their origin in print media, the computer of the near future will provide more flexible visual computer interfaces in which diagrams adapt to their viewing context, support interactive exploration and provide semantics-based retrieval and adaptation. We provide an overview of the Adaptive Diagram Research Project whose aim is to provide a generic computational basis for this new type of diagrams.

This paper places concurrent rewriting in the perspective of supporting the development and use of computational systems. We briefly recall the usefulness of computational systems (i.e. a rewriting theory with strategies) as a logical framework. We then show that the right implementation model for concurrent rewriting allows us to give a meaning to the concurrent rewrite of overlapping redexes. The principles of the implementation of concurrent rewriting and of the associated garbage collection are sketched. We then present a specific transformation of conditional rewriting to unconditional rewriting, that permits us to preserve the potential concurrency of the system as much as possible. This allows us to extend the ReCo system to handle conditional specifications. We finally present experimental results of the system on various parallel architectures.

An equational formula is a first order formula over an alphabet F of function symbols and the equality predicate symbol. Such formulae are interpreted in the algebra T(F) of finite trees. An equational formula is w.e.d. (without equations in disjunctions) if its solved forms do not contain any subformula s = t V u ≠ v. A unification problem is any equational problem which does not contain any negation (in particular, it should not contain any disequation). We give a terminating set of transformation rules such that a w.e.d. formula φ is (semantically) equivalent to a unification problem iff its irreducible forn is a unification problem. This result can be formulated in another way: our set of transformation rules computes a finite complete set of “most general unifiers” for a w.e.d. formula each time such a finite set exists. Such results extend Lassez and Marriott results on “explicit representation of terms defined by counter-examples” [10]. The above results are extended to quotients of the free algebra by a congruence =e which can be generated by a set of shallow permulative equations E.

Abstract

This paper presents a line of research in genetic algorithms (GAs), called building-block identification. The building blocks (BBs) are common structures inferred from a set of solutions. In simple GA, crossover operator plays an important role in mixing BBs. However, the crossover probably disrupts the BBs because the cut point is chosen at random. Therefore the BBs need to be identified explicitly so that the solutions are efficiently mixed. Let S be a set of binary solutions and the solution s = b₁ ... b_ℓ,   b_i ∈ {0, 1}. We construct a symmetric matrix of which the element in row i and column j, denoted by m_ij, is the chi-square of variables b_i and b_j. The larger the m_ij is, the higher the dependency is between bit i and bit j. If m_ij is high, bit i and bit j should be passed together to prevent BB disruption. Our approach is validated for additively decomposable functions (ADFs) and hierarchically decomposable functions (HDFs). In terms of scalability, our approach shows a polynomial relationship between the number of function evaluations required to reach the optimum and the problem size. A comparison between the chi-square matrix and the hierarchical Bayesian optimization algorithm (hBOA) shows that the matrix computation is 10 times faster and uses 10 times less memory than constructing the Bayesian network.

Many logic programming based approaches can be used to describe and solve combinatorial search problems. On the one hand there is constraint logic programming which computes a solution as an answer substitution to a query containing the variables of the constraint satisfaction problem. On the other hand there are systems based on stable model semantics, abductive systems, and first order logic model generators which compute solutions as models of some theory. This paper compares these different approaches from the point of view of knowledge representation (how declarative are the programs) and from the point of view of performance (how good are they at solving typical problems).

Abstract

More than new algorithms, proofs, or technologies, it is the emergence of definitions that has changed the landscape of cryptography. We describe how definitions work in modern cryptography, giving a number of examples, and we provide observations, opinions, and suggestions about the art and science of crafting them.

Abstract

Logic programs with ordered disjunctions (LPODs) are natural vehicles for expressing choices that have a preference ordering. They are extensions of the familiar extended logic programs that have answer sets as semantics. In game theory, players usually prefer strategies that yield higher payoffs. Since strategies are choices, LPODs would seem to be a suitable logical formalism for expressing some game-theoretic properties. This paper shows how pure strategy normal form games can be encoded as LPODs in such a way that the answer sets that are mutually most preferred by all players are exactly the Nash equilibria. A similar result has been obtained by researchers using a different, but related, logical formalism, viz., ordered choice logic programs that were used to encode extensive games.

Abstract

In robot visual servoing, only the conception of image Jacobian is traditionally utilized, which indicates that the image feature varies only with the robot motion. But for a moving object, the image feature can be affected both by the robot motion and by the object motion. In this paper total Jacobian and object Jacobian are defined. The total Jacobian matrix, consisting of image Jacobian and object Jacobian, is estimated using exponentially weighted least square algorithm. No calibration is required. The control scheme is image Jacobian pseudo-inverse appending an item related to the object motion. Re-sults for both two and six degree-of-freedom systems demonstrate the success of the algorithm.

This paper presents a declarative semantics which exhibits the termination properties of a logic program. The semantics associates a program with its binary unfoldings — a possibly infinite set of binary clauses. Termination of a program P and goal G is indicated by the absence of an infinite chain in the binary unfoldings of P starting with G. The main contribution is a formal semantic basis for the termination analysis of logic programs which facilitates both design and implementation. As an implementation vehicle we propose a simple meta-interpreter for binary unfoldings and the use of an abstract domain based on symbolic norm constraints. Many of the recently proposed termination analyses for logic programs can be expressed concisely within our approach. To demonstrate our approach we have reformulated the analysis originally described in [13]. The implementation uses a standard library for linear equations over the recels. The combination of binary unfoldings and a constraint solver is shown to significantly simplify the design of the analysis.

Oz is a concurrent constraint language providing for firstclass procedures, concurrent objects, and encapsulated search. DFKI Oz is an interactive implementation of Oz competitive in performance with commercial Prolog and Lisp systems. This paper describes Amoz, the abstract machine underlying DFKI Oz. Amoz implements rational tree constraints, first-class procedures, local computation spaces for deep guards, and preemptive and fair threads.

Abstract

A central problem in extending the von Neumann architecture to petaflop computers with a shared memory and millions of hardware threads is defining the memory model [1, 2, 3]. Such a model must specify the behavior of concurrent (conditional) reads and writes to the same memory locations. We present a simple, general framework for the specification of memory models based on an abstract machine that uses sets of order and value constraints to communicate between threads and main memory. Memory is permitted to specify exactly those linkings (mappings from read events to write events) which result in a unique solution for the constraints, and hence forces a unique patterns of bits to flow from writes to reads.

We show that this single principle accounts for almost all the “causality test cases” proposed for the java memory model. It may be used as the basis for developing a formal memory model for the java programming language.

An implementation of CCMs in a Prolog-based constraint language has been developed by Tom Schrijvers and Bart Demoen [4]. This paper is a summary of [5].

This paper focuses on one of the key steps in the design of semantic based analyses for logic programs — the definition of an abstract unification algorithm for a given notion of data description. We survey some of the major notions of data descriptions proposed in the context of mode and sharing analyses. We demonstrate how a careful and systematic analysis of the underlying concrete unification algorithm contributes to the design of the abstract algorithm. Several relevant properties of concrete substitutions which influence the design of abstract domains and algorithms are described. We make use of a novel representation called abstract equation systems to uniformly represent a a wide range of data descriptions for such analyses proposed in the literature.

We present a language for integrating probabilistic reasoning and logic programming. The key idea is to use constraints based techniques such as the constraints store and finite domain variables. First we show how these techniques can be used to integrate a number of probabilistic inference algorithms with logic programming. We then proceed to detail a language which effects conditioning by probabilistically partitioning the constraint store. We elucidate the kinds of reasoning effected by the introduced language by means of two well known probabilistic problems: the three prisoners and Monty Hall. In particular we show how the syntax of the language can be used to avoid the pitfalls normally associated with the two problems. An elimination algorithm for computing the probability of a query in a given store is presented.

A major impediment for more widespread use of offline partial evaluation is the difficulty of obtaining and maintaining annotations for larger, realistic programs. Existing automatic binding-time analyses still only have limited applicability and annotations often have to be created or improved and maintained by hand, leading to errors. We present a technique to help overcome this problem by using online control techniques which supervise the specialisation process in order to detect such errors. We discuss an implementation in the logen system and show on a series of examples that this approach is effective: very few false alarms were raised while infinite loops were detected quickly. We also present the integration of this technique into a web interface, which highlights problematic annotations directly in the source code. A method to automatically fix incorrect annotations is presented, allowing the approach to be also used as a pragmatic binding time analysis. Finally we show how our method can be used for efficiently locating errors with built-ins inside Prolog source code.

Lattice protein models are used for hierarchical approaches to protein structure prediction, as well as for investigating principles of protein folding. So far, one has the problem that there exists no lattice that can model real protein conformations with good quality and for which an efficient method to find native conformations is known.

We present the first method for the FCC-HP-Model [3] that is capable of finding native conformations for real-sized HP-sequences. It has been shown [23] that the FCC lattice can model real protein conformations with coordinate root mean square deviation below 2 Å.

Our method uses a constraint-based approach. It works by first calculating maximally compact sets of points (hydrophobic cores), and then threading the given HP-sequence to the hydrophobic cores such that the core is occupied by H-monomers.

The specification of the Java Memory Model (jmm) is phrased in terms of acceptors of execution sequences rather than the standard generative view of operational semantics. This creates a mismatch with language-based techniques, such as simulation arguments and proofs of type safety.

We describe a semantics for the jmm using standard programming language techniques that captures its full expressivity. For data-race-free programs, our model coincides with the jmm. For lockless programs, our model is more expressive than the jmm. The stratification properties required to avoid causality cycles are derived, rather than mandated in the style of the jmm.

The jmm is arguably non-canonical in its treatment of the interaction of data races and locks as it fails to validate roach-motel reorderings and various peephole optimizations. Our model differs from the jmm in these cases. We develop a theory of simulation and use it to validate the legality of the above optimizations in any program context.

In this paper, we revisit the evidential reasoning (ER) approach to multiple-attribute decision making (MADM) with uncertainty. The attribute aggregation problem in MADM under uncertainty is generally formulated as a problem of evidence combination. Then several new aggregation schemes are proposed and simultaneously their theoretical features are explored. A numerical example traditionally examined in published sources on the ER approach is used to illustrate the proposed techniques.

Recent studies have started to explore context-awareness as a driver in the design of adaptable business processes. The emerging challenge of identifying and considering contextual drivers in the environment of a business process are well understood, however, typical methods and models for business process design do not yet consider this context. In this paper, we describe our work on the design of a method framework and appropriate models to enable a context-aware process design approach. We report on our ongoing work with an Australian insurance provider and describe the design science we employed to develop innovative and useful artifacts as part of a context-aware method framework. We discuss the utility of these artifacts in an application in the claims handling process at the case organization.

In many Constraint Logic Programming (CLP) applications one needs to express not only strict requirements but also preferences. Constraint hierarchies are one way of describing preferred criteria in the statement of a problem. In [18] CLP was extended to integrate constraint hierarchies resulting in Hierarchical Constraint Logic Programming (HCLP). We propose an alternative approach for describing preferred criteria in CLP as a problem of relational optimization (RO). In this approach the programmer defines a preference relation which indicates when a solution is better than another solution. We study several schemes based on pruning for optimizing an objective function, and we show how these schemes can be generalized to handle preference relations defined by CLP programs, while preserving a straightforward logical semantics. Further we show on some examples that the greater flexibility of the relational optimization scheme is not at the cost of efficiency.

We consider the scheme of indefinite constraint databases proposed by Koubarakis. This scheme can be used to represent indefinite information arising in temporal, spatial and truly spatiotemporal applications. The main technical problem that we address in this paper is the discovery of tractable classes of databases and queries in this scheme. We start with the assumption that we have a class of constraints C with satisfiability and variable elimination problems that can be solved in PTIME. Under this assumption, we show that there are several general classes of databases and queries for which query evaluation can be done with PTIME data complexity. We then search for tractable instances of C in the area of temporal and spatial constraints. Classes of constraints with tractable satisfiability problems can be easily found in the literature. The largest class that we consider is the class of Horn disjunctive linear constraints over the rationals. Because variable elimination for Horn disjunctive linear constraints cannot be done in PTIME, we try to discover subclasses with tractable variable elimination problems. The class of UTVPI^≠ constraints is the largest class that we show to have this property. Finally, we restate the initial general results with C ranging over the newly discovered tractable classes. Tractable query answering problems for indefinite temporal and spatial constraint databases are identified in this way.

In this paper, we propose a design exploration framework which consider impreciseness in design specification. In high-level synthesis, imprecise information is often encountered. Two kinds of impreciseness are considered here: imprecise characteristics of functional units and imprecise design constraints. The proposed design exploration framework is based on efficient scheduling algorithm which considers impreciseness, Register-Constrained Inclusion Scheduling. We demonstrate the effectiveness of our framework by exploring a design solution for a well-known benchmark, Voltera filter. The selected solution meets the acceptability criteria while minimizing the total number of registers.

Reasoning about time is a very ancient discipline, perhaps as old as prehistoric man. These ancient humans had discovered how long to roast their hunted meat and how to dry and age the skins of animals. They learned how and when to plant seeds, and were guided by the cycles of the sun, moon and the seasons. Our ancestors knew that day followed night and night followed day, and they had some notion of duration of day and night. This basic temporal knowledge was exploited to develop a sense of planning, taking advantage of observation and experience. For example, they would have observed that deer drink at the river at a certain time of the day, or that .sh are easier to catch in the early morning. Early humans could recognize the changing seasons, and adapted their behavior in order to expect and avoid some of the dangers of cold and hunger by preparing in advance.

An important amount of research has been devoted to consistent view updating. In this paper we propose a new approach to deal with this problem. Our approach is aimed at obtaining intensional translations that satisfy a view update request, instead of obtaining extensional translations. Intuitively, our translations are intensional in the sense that they characterise multiple possible values for a set of base fact updates such that the request is satisfied when the updates are applied using these values. Each characterised set of updates constitutes an extensional translation. The main advantages of following this approach are to improve the meaningfulness of the translations to the users; to facilitate the treatment of infinite domains; and to reduce the search space needed to obtain the translations.

Abstract

Reasoning about time is a very ancient discipline, perhaps as old as prehistoric man. These ancient humans had discovered how long to roast their hunted meat and how to dry and age the skins of animals. They learned how and when to plant seeds, and were guided by the cycles of the sun, moon and the seasons. Our ancestors knew that day followed night and night followed day, and they had some notion of duration of day and night. This basic temporal knowledge was exploited to develop a sense of planning, taking advantage of observation and experience. For example, they would have observed that deer drink at the river at a certain time of the day, or that .sh are easier to catch in the early morning. Early humans could recognize the changing seasons, and adapted their behavior in order to expect and avoid some of the dangers of cold and hunger by preparing in advance.

Abstract

This paper describes a proxy signature scheme where a signer can delegate a partial signing right to a party who can then sign on behalf of the original signer to generate a partial proxy signature. A partial proxy signature can be converted into a full signature with the aid of the original signer. Our proxy signature scheme has the feature of deniability, i.e., only the designated receiver can verify the partial proxy signature and the full signature associated to him, while they are not transferable. This paper also describes an application of our scheme in a deniable optimistic fair exchange.

Abstract

We present a language for integrating probabilistic reasoning and logic programming. The key idea is to use constraints based techniques such as the constraints store and finite domain variables. First we show how these techniques can be used to integrate a number of probabilistic inference algorithms with logic programming. We then proceed to detail a language which effects conditioning by probabilistically partitioning the constraint store. We elucidate the kinds of reasoning effected by the introduced language by means of two well known probabilistic problems: the three prisoners and Monty Hall. In particular we show how the syntax of the language can be used to avoid the pitfalls normally associated with the two problems. An elimination algorithm for computing the probability of a query in a given store is presented.

Abstract

In this paper, we propose a design exploration framework which consider impreciseness in design specification. In high-level synthesis, imprecise information is often encountered. Two kinds of impreciseness are considered here: imprecise characteristics of functional units and imprecise design constraints. The proposed design exploration framework is based on efficient scheduling algorithm which considers impreciseness, Register-Constrained Inclusion Scheduling. We demonstrate the effectiveness of our framework by exploring a design solution for a well-known benchmark, Voltera filter. The selected solution meets the acceptability criteria while minimizing the total number of registers.

Keywords: Imprecise Design Exploration, Scheduling/Allocation, Multiple design attributes, Imprecise information, Register constraint, Inclusion Scheduling.

Abstract

Cyber security is a serious global concern. The potential of cyber terrorism has posed a threat to national security; meanwhile the increasing prevalence of malware and incidents of cyber attacks hinder the utilization of the Internet to its greatest benefit and incur significant economic losses to individuals, enterprises, and public organizations. This paper presents some recent advances in intrusion detection, feature selection, and malware detection.

In intrusion detection, stealthy and low profile attacks that include only few carefully crafted packets over an extended period of time to delude firewalls and the intrusion detection system (IDS) have been difficult to detect. In protection against malware (trojans, worms, viruses, etc.), how to detect polymorphic and metamorphic versions of recognized malware using static scanners is a great challenge.

We present in this paper an agent based IDS architecture that is capable of detecting probe attacks at the originating host and denial of service (DoS) attacks at the boundary controllers. We investigate and compare the performance of different classifiers implemented for intrusion detection purposes. Further, we study the performance of the classifiers in real-time detection of probes and DoS attacks, with respect to intrusion data collected on a real operating network that includes a variety of simulated attacks.

Feature selection is as important for IDS as it is for many other modeling problems. We present several techniques for feature selection and compare their performance in the IDS application. It is demonstrated that, with appropriately chosen features, both probes and DoS attacks can be detected in real time or near real time at the originating host or at the boundary controllers.

We also briefly present some encouraging recent results in detecting polymorphic and metamorphic malware with advanced static, signature-based scanning techniques.

Abstract

Since its introduction, broadcast encryption has attracted many useful applications. In this paper, we propose two identity-based schemes for authenticated broadcasting and distributed message authentication. The first scheme supports multiple broadcasters and allows each broadcaster to dynamically broadcast messages into an arbitrary group of receivers determined by the broadcaster. The receivers can obtain the broadcasted message using the identity of the broadcaster and his own secret decryption key; hence it ensures both confidentiality and authenticity of the message. The second scheme allows users (receivers) to send messages back to the broadcaster where the authentication of messages is done with the identity of the user. We also provide security proofs for our schemes under the random oracle model.

Abstract

In this paper, we study exact learning of logic programs from entailment queries and present a polynomial time algorithm to learn a rich class of logic programs that allow local variables and include many standard programs like addition, multiplication, exponentiation, member, prefix, suffix, length, append, merge, split, delete, insert, insertion-sort, quick-sort, merge-sort, preorder and inorder traversal of binary trees, polynomial recognition, derivatives, sum of a list of naturals. Our algorithm asks at most polynomial number of queries and our class is the largest of all the known classes of programs learnable from entailment.

Abstract

The fast vector space and probabilistic methods use the term counts and the slower proximity methods use term positions. We present the spectral-based information retrieval method which is able to use both term count and position information to obtain high precision document rankings. We are able to perform this, in a time comparable to the vector space method, by examining the query term spectra rather than query term positions. This method is a generalisation of the vector space method (VSM). Therefore, our spectral method can use the weighting schemes and enhancements used in the VSM.

Abstract

This paper presents a Thai syllable speech recognition system with the capability to achieve high accuracy of Thai syllable speech and Thai tone recognition. The recognition accuracy of 97.84% is achieved for Thai syllable speech recognition using the Continuous Density Hidden Markov Model (CDHMM). To provide a faster response, a beam pruning technique is applied, in which the result shows that by using this technique with an appropriate beam width, the recognition time can be reduced by more than 4 times. As Thai is tonal language, tone recognition is crucial for distinguishing meanings of Thai syllables. To obtain high rates of tone recognition in the Thai language, the CDHMM and a mixed acoustic feature method are employed. The tone recognition rates of 97.88%, 97.36%, 98.81%, 90.67% and 100.0% are achieved for mid, low, falling, high and rising tones, respectively.

Abstract

In this paper, we propose a new robust content-based musical genre classification and retrieval algorithm using multi-feature clustering (MFC) method. In contrast to previous works, this paper focuses on two practical issues of the system dependency problem on different input query patterns (or portions) and input query lengths which causes serious uncertainty of the system performance. In order to solve these problems, a new approach called multi-feature clustering (MFC) based on k-means clustering is proposed. To verify the performance of the proposed method, several excerpts with variable duration were extracted from every other position in a queried music file. Effectiveness of the system with MFC and without MFC is compared in terms of the classification and retrieval accuracy. It is demonstrated that the use of MFC significantly improves the system stability of musical genre classification and retrieval performance with higher accuracy rate.

Abstract

Proving the unsatisfiability of propositional Boolean formulas has applications in a wide range of fields. Minimal Unsatisfiable Sets (MUS) are signatures of the property of unsatisfiability in formulas and our understanding of these signatures can be very helpful in answering various algorithmic and structural questions relating to unsatisfiability. In this paper, we explore some combinatorial properties of MUS and use them to devise a classification scheme for MUS. We also derive bounds on the sizes of MUS in Horn, 2-SAT and 3-SAT formulas.

Keywords: Boolean formulas, propositional logic, satisfiability, Minimal Unsatisfiable Sets.