Download Automata for Branching and Layered Temporal Structures: An by Gabriele Puppis PDF

By Gabriele Puppis

Since 2002, FoLLI awards an annual prize for an exceptional dissertation within the fields of common sense, Language, and knowledge. This publication relies at the Ph.D. thesis of Gabriele Puppis, who used to be the winner of the E.W. Beth dissertation award for 2007.

Puppis' thesis makes a speciality of good judgment and Computation and, extra in particular, on automata-based decidability thoughts for time granularity and on a brand new procedure for identifying Monadic moment Order theories of timber. the consequences provided signify an important step in the direction of a greater knowing of the alterations in granularity degrees that people make so simply in cognition of time, area, and different phenomena, while their logical and computational constitution poses tricky conceptual and computational challenges.

Show description

Read Online or Download Automata for Branching and Layered Temporal Structures: An Investigation into Regularities of Infinite Transition Systems PDF

Best computers books

The Ni-YSZ interface

The anode/electrolyte interface ш good oxide gas cells (SOFC) is understood to reason electric losses. Geometrically easy Ni yttria-stabilised zirconia (YSZ) interfaces have been tested to achieve details at the structural and chemical adjustments happening in the course of experiments at 1000°C in an environment of ninety seven% H2/3% H20.

Handbook of Computer Vision and Applications, V1

The instruction manual of machine imaginative and prescient and purposes, Three-Volume Set is on one of many "hottest" topics in present day intersection of utilized Physics, desktop technological know-how, electric Engineering, and utilized arithmetic. the distinctiveness of this set is that it's very applications-oriented. Examples of functions in numerous fields of contemporary technological know-how are quite emphasised.

Extra resources for Automata for Branching and Layered Temporal Structures: An Investigation into Regularities of Infinite Transition Systems

Sample text

Below, for w the sake of brevity, we write (s, c) −−→ (s , c ) to denote the existence of a partial run of an NCSSA A that starts from the configuration (s, c), reaches the configuration (s , c ), and recognizes the finite word w. Similarly, we write w (s, c) −−→ whenever A recognizes the infinite word w starting from the configuration (s, c). Lemma 2. Let A = (A, SA , Sε , Ω, δ, γ, s0 , c0 ) be an NCSSA, s a unlabeled state, and c : Sε → N ∪ {ω} a valuation such that c(s) > 0 and c(r) = c0 (r) + for every unlabeled state r such that (r, s) ∈ ΓA .

A A It is now clear that A recognizes the word uA s0 uδ(s0 ) ... uδn (s0 ) . 2 Algorithms on NCSSA In this section, we exploit the nested structure of NCSSA transition functions (precisely, Proposition 3), to devise efficient algorithms that operate on NCCSA. In particular, we will show that, under suitable conditions, granule conversion problems can be solved in polynomial time with respect to the size of NCSSA-based representations of time granularities. We will also provide a non-deterministic polynomial-time solution to the (non-)equivalence problem for NCSSA.

5b. In order to guarantee termination, one can exploit the fact that A recognizes an ultimately periodic word w. More precisely, by reasoning on the initial and repeating patterns of w, one can detect whether a non-terminating loop has been reached and, accordingly, return the (possibly infinite) set T of converted time points as a linear progression of the form X ∪ {m + n q : m ∈ Y, n ∈ N}, where X, Y are finite disjoint sets of natural numbers and q is a positive natural number. A similar idea can be applied if X is an infinite set of granules represented by a linear progression.

Download PDF sample

Rated 4.89 of 5 – based on 24 votes