1,721,010 research outputs found
A note on coding techniques in bounded arithmetic
No full textTechnical Report n. 231, Dipartimento di Matematica, Via del Capitano 15, Sien
On the commutative equivalence of semi-linear sets of N^k
No full textAbstract Given two subsets S1,S2 of Nk, we say that S1 is commutatively equivalent to S2 if there exists a bijection f:S1⟶S2 from S1 onto S2 such that, for every v∈S1, |v|=|f(v)|, where |v| denotes the sum of the components of v. We prove that every semi-linear set of Nk is commutatively equivalent to a recognizable subset of Nk
Generating graphical applications from state-transition visual specifications
No full textIn graphical applications, visual representations are mostly used in an ad hoc fashion with little or no underlying formal support. Due to this, no common methodology for handling visual and diagrammatic representations has emerged and formal techniques for their support are underdeveloped. Usually, a programmer develops a graphical application by applying a general-purpose visual programming environment and ad hoc implementing the application requirements. Then, big efforts are often required when the application has to be successively modified or extended. In this paper, we present a finite-automaton-based formalism for the specification of rapid application development (RAD) visual applications, which provides a formal basis in the visual application generation. A prototype tool, based on this approach, has been developed and it is currently being experimented on a variety of case studies
UPMurphi: a Tool for Universal Planning on PDDL+ Problems
No full textSystems subject to (continuous) physical effects and controlled
by (discrete) digital equipments, are today very common.
Thus, many realistic domains where planning is required
are represented by hybrid systems, i.e., systems containing
both discrete and continuous values, with possibly a
nonlinear continuous dynamics. The PDDL+ language allows
one to model these domains, however the current tools
can generally handle only planning problems on (possibly
hybrid) systems with linear dynamics. Therefore, universal
planning applied to hybrid systems and, in general, to nonlinear
systems is completely out of scope for such tools. In
this paper, we propose the use of explicit model checkingbased
techniques to solve universal planning problems on
such hardly-approachable domains
Cost-Optimal Strong Planning in Non-Deterministic Domains
No full textMany real world domains present a non-deterministic behaviour, mostly due to unpredictable environmental conditions. In this context, strong planning, i.e., finding a plan which is guaranteed to achieve the goal regardless of non-determinism, is a significant research challenge for both the planning and the control communities. In particular, the problem of cost-optimal strong planning has not been addressed so far. In this paper we provide a formal description of the cost-optimal strong planning problem in non-deterministic finite state systems, present an algorithm to solve it with good complexity bounds and formally prove the correctness and completeness of the proposed algorithm. Furthermore, we present experimental results showing the effectiveness of the proposed approach on a meaningful case study
A Probabilistic Approach to Automatic Formal Verification
No full textThe main obstruction to automatic verification of Concurrent Systems is is the huge amount of memory required to complete the verification task (state explosion). In fact when the memory is over we are forced to abandon our verification effort, even when we are somehow close to finish it. We believe that waiting longer for a reasonable answer is better than being left with an out of memory message and no answer at all. Thus in this paper we present a probabilistic algorithm for Explicit State Space Exploration.
Our algorithm trades space with time. In particular when our memory is over our algorithm does not give up verification. It just proceeds at a lower speed and its results will only hold with some arbitrarily small error probability.
Our preliminary experimental results show that using our probabilistic algorithm we can typically save more than 30% of RAM with an average time penalty of about 100% w.r.t. a deterministic state space exploration
Synthesis of Optimal Control Systems: a Comparison between Model Checking and Dynamic Programming Techniques
No full textA PDDL+ Benchmark Problem: The Batch Chemical Plant
No full textThe PDDL+ language has been mainly devised to allow
modelling of real-world systems, with continuous, timedependant
dynamics. Several interesting case studies with
these characteristics have been also proposed, to test the language
expressiveness and the capabilities of the support tools.
However, most of these case studies have not been completely
developed so far. In this paper we focus on the batch chemical
plant case study, a very complex hybrid system with nonlinear
dynamics that could represent a challenging benchmark
problem for planning techniques and tools. We present a
complete PDDL+ model for such system, and show an example
application where the UPMurphi universal planner is
used to generate a set of production policies for the plant
On the commutative equivalence of bounded context-free and regular languages: the code case
Full text linkAbstract This is the first paper of a group of three where we prove the following result. Let A be an alphabet of t letters and let ψ:A⁎⟶Nt be the corresponding Parikh morphism. Given two languages L1,L2⊆A⁎, we say that L1 is commutatively equivalent to L2 if there exists a bijection f:L1⟶L2 from L1 onto L2 such that, for every u∈L1, ψ(u)=ψ(f(u)). Then every bounded context-free language is commutatively equivalent to a regular language
- …
