Abstract: Sudoku is a kind of logic puzzles. Each puzzle consists
of a board, which is a 9×9 cells, divided into nine 3×3 subblocks
and a set of numbers from 1 to 9. The aim of this puzzle is to
fill in every cell of the board with a number from 1 to 9 such
that in every row, every column, and every subblock contains each
number exactly one. Sudoku puzzles belong to combinatorial problem
(NP complete). Sudoku puzzles can be solved by using a variety of
techniques/algorithms such as genetic algorithms, heuristics, integer
programming, and so on. In this paper, we propose a new approach for
solving Sudoku which is by modelling them as block-world problems.
In block-world problems, there are a number of boxes on the table
with a particular order or arrangement. The objective of this problem
is to change this arrangement into the targeted arrangement with the
help of two types of robots. In this paper, we present three models
for Sudoku. We modellized Sudoku as parameterized multi-agent
systems. A parameterized multi-agent system is a multi-agent system
which consists of several uniform/similar agents and the number of
the agents in the system is stated as the parameter of this system. We
use Temporal Logic of Actions (TLA) for formalizing our models.
Abstract: In mobile environments, unspecified numbers of transactions
arrive in continuous streams. To prove correctness of their
concurrent execution a method of modelling an infinite number of
transactions is needed. Standard database techniques model fixed
finite schedules of transactions. Lately, techniques based on temporal
logic have been proposed as suitable for modelling infinite schedules.
The drawback of these techniques is that proving the basic
serializability correctness condition is impractical, as encoding (the
absence of) conflict cyclicity within large sets of transactions results
in prohibitively large temporal logic formulae. In this paper, we show
that, under certain common assumptions on the graph structure of
data items accessed by the transactions, conflict cyclicity need only
be checked within all possible pairs of transactions. This results in
formulae of considerably reduced size in any temporal-logic-based
approach to proving serializability, and scales to arbitrary numbers
of transactions.
Abstract: The objective of the paper is twofold. First, to develop a
formal framework for planning for mobile agents. A logical language
based on a temporal logic is proposed that can express a type of
tasks which often arise in network management. Second, to design a
planning algorithm for such tasks. The aim of this paper is to study
the importance of finding plans for mobile agents. Although there
has been a lot of research in mobile agents, not much work has been
done to incorporate planning ideas for such agents. This paper makes
an attempt in this direction. A theoretical study of finding plans for
mobile agents is undertaken. A planning algorithm (based on the
paradigm of mobile computing) is proposed and its space, time, and
communication complexity is analyzed. The algorithm is illustrated
by working out an example in detail.
Abstract: In recent past, the Unified Modeling Language (UML) has become the de facto industry standard for object-oriented modeling of the software systems. The syntax and semantics rich UML has encouraged industry to develop several supporting tools including those capable of generating deployable product (code) from the UML models. As a consequence, ensuring the correctness of the model/design has become challenging and extremely important task. In this paper, we present an approach for automatic verification of protocol model/design. As a case study, Session Initiation Protocol (SIP) design is verified for the property, “the CALLER will not converse with the CALLEE before the connection is established between them ". The SIP is modeled using UML statechart diagrams and the desired properties are expressed in temporal logic. Our prototype verifier “UML-SMV" is used to carry out the verification. We subjected an erroneous SIP model to the UML-SMV, the verifier could successfully detect the error (in 76.26ms) and generate the error trace.
Abstract: We present an operator for a propositional linear temporal logic over infinite schedules of iterated transactions, which, when applied to a formula, asserts that any schedule satisfying the formula is serializable. The resulting logic is suitable for specifying and verifying consistency properties of concurrent transaction management systems, that can be defined in terms of serializability, as well as other general safety and liveness properties. A strict form of serializability is used requiring that, whenever the read and write steps of a transaction occurrence precede the read and write steps of another transaction occurrence in a schedule, the first transaction must precede the second transaction in an equivalent serial schedule. This work improves on previous work in providing a propositional temporal logic with a serializability operator that is of the same PSPACE complete computational complexity as standard propositional linear temporal logic without a serializability operator.
Abstract: Existing work in temporal logic on representing the
execution of infinitely many transactions, uses linear-time temporal
logic (LTL) and only models two-step transactions. In this paper,
we use the comparatively efficient branching-time computational tree
logic CTL and extend the transaction model to a class of multistep
transactions, by introducing distinguished propositional variables
to represent the read and write steps of n multi-step transactions
accessing m data items infinitely many times. We prove that the
well known correspondence between acyclicity of conflict graphs
and serializability for finite schedules, extends to infinite schedules.
Furthermore, in the case of transactions accessing the same set of
data items in (possibly) different orders, serializability corresponds
to the absence of cycles of length two. This result is used to give an
efficient encoding of the serializability condition into CTL.
Abstract: Most of the concurrent transactional protocols consider
serializability as a correctness criterion of the transactions execution.
Usually, the proof of the serializability relies on mathematical proofs
for a fixed finite number of transactions. In this paper, we introduce
a protocol to deal with an infinite number of transactions which are
iterated infinitely often. We specify serializability of the transactions
and the protocol using a specification language based on temporal
logics. It is worthwhile using temporal logics such as LTL (Lineartime
Temporal Logic) to specify transactions, to gain full automatic
verification by using model checkers.
Abstract: Validation of an automation system is an important issue. The goal is to check if the system under investigation, modeled by a Petri net, never enters the undesired states. Usually, tools dedicated to Petri nets such as DESIGN/CPN are used to make reachability analysis. The biggest problem with this approach is that it is impossible to generate the full occurence graph of the system because it is too large. In this paper, we show how computational methods such as temporal logic model checking and Groebner bases can be used to verify the correctness of the design of an automation system. We report our experimental results with two automation systems: the Automated Guided Vehicle (AGV) system and the traffic light system. Validation of these two systems ranged from 10 to 30 seconds on a PC depending on the optimizing parameters.