FREE ELECTRONIC LIBRARY - Thesis, documentation, books

Pages:   || 2 | 3 |

«Abstract. Automated reasoning about systems with infinite domains requires an extension of regular automata to infinite alphabets. Existing ...»

-- [ Page 1 ] --

Variable Automata over Infinite Alphabets

Orna Grumberg1, Orna Kupferman2, and Sarai Sheinvald2

Department of Computer Science, The Technion, Haifa 32000, Israel

School of Computer Science and Engineering, Hebrew University, Jerusalem 91904, Israel

Abstract. Automated reasoning about systems with infinite domains requires an

extension of regular automata to infinite alphabets. Existing formalisms of such

automata cope with the infiniteness of the alphabet by adding to the automaton a set of registers or pebbles, or by attributing the alphabet by labels from an auxiliary finite alphabet that is read by an intermediate transducer. These formalisms involve a complicated mechanism on top of the transition function of automata over finite alphabets and are therefore difficult to understand and to work with.

We introduce and study variable finite automata over infinite alphabets (VFA).

VFA form a natural and simple extension of regular (and ω-regular) automata, in which the alphabet consists of letters as well as variables that range over the infinite alphabet domain. Thus, VFAs have the same structure as regular automata, only that some of the transitions are labeled by variables. We compare VFA with existing formalisms, and study their closure properties and classical decision problems. We consider the settings of both finite and infinite words. In addition, we identify and study the deterministic fragment of VFA. We show that while this fragment is sufficiently strong to express many interesting properties, it is closed under union, intersection, and complementation, and its nonemptiness and containment problems are decidable. Finally, we describe a determinization process for a determinizable subset of VFA.

1 Introduction Automata-based formal methods are successfully applied in automated reasoning about systems. When the systems are finite-state, their behaviors and specifications can be modeled by finite automata. When the systems are infinite-state, reasoning is undecidable, and research is focused on identifying decidable special cases (e.g., pushdown systems) and on developing heuristics (e.g., abstraction) for coping with the general case.

One type of infinite-state systems, motivating this work, are systems in which the control is finite and the source of infinity is data. This includes, for example, software with integer parameters [3], datalog systems with infinite data domain [15, 4], and XML documents, whose leaves are typically associated with data values from some infinite domain [7, 5]. Lifting automata-based methods to the setting of such systems requires the introduction of automata with infinite alphabets. 3 The transition function of a nondeterministic automaton over finite alphabets (NFA) maps a state q and a letter σ to a set of states the automaton may move to when it is in Different approaches for automatically reasoning about such systems are based on extensions of first-order logic [2] and linear temporal logics [8].

2 O. Grumberg, O. Kupferman, and S. Sheinvald state q and the letter in the input is σ. When the alphabet of the automaton is infinite, specifying all transitions is impossible, and a new formalism is needed in order to represent them in a finite manner. Existing formalisms of automata with infinite alphabets fulfill this task by augmenting the automaton by registers or pebbles, or by attributing the alphabet by labels from an auxilary finite alphabet that is read by an intermediate transducer. We elaborate of the existing formalisms below.

A register automaton [13] has a finite set of registers, each of which may contain a letter from the infinite alphabet. The transitions of a register automaton compare the letter in the input with the content of the registers, and may also store the input letter in a register. Several variants of this model have been studied. For example, [10] forces the content of the registers to be different, [12] adds alternation and two-wayness, and [9] allows the registers to change their content nondeterministically during the run.

A pebble automaton [12] places pebbles on the input word in a stack-like manner.

The transitions of a pebble automaton compare the letter in the input with the letters in positions marked by the pebbles. Several variants of this model have been studied. For example, [12] studies alternating and two-way pebble automata, and [14] introduces top-view weak pebble automata.

The newest formalism is data automata [2, 1]. For an infinite alphabet Σ, a data automaton runs on data words, which are words over the alphabet Σ × F, where F is a finite auxilary alphabet. Intuitively, the finite alphabet is accessed directly, while the infinite alphabet can only be tested for equality, and is used for inducing an equivalence relation on the set of positions. Technically, a data automaton consists of two components. The first is a letter-to-letter transducer that runs on the projection of the input word on F and generates words over yet another alphabet Γ. The second is a regular automaton that runs on subwords (determined by the equivalence classes) of the word generated by the transducer.

The quality of a formalism is measured by its simplicity, expressive power, compositionality, and computability. In simplicity, we refer to the effort required in order to understand a given automaton, work with it, and implement it. In compositionality, we refer to closure under the basic operations of union, intersection, and complementation.

In computability, we refer to the decidability and complexity of classical problems like nonemptiness, membership, universality, and containment.

The formalisms of register, pebble, and data automata all fail hard the simplicity criterion. Augmenting NFAs with registers or pebbles requires a substantial modification of the transition function. The need to maintain the registers and pebbles makes the automata hard to understand and work with. Unfortunately, most researchers in the formal-method community are not familiar with register and pebble automata. Indeed, even the definition of the basic notion of a run of such automata cannot simply rely on the familiar definition of a run of an NFA, and involves the notions of configurations, successive configurations, and so on, with no possible shortcuts.

Data automata do not come to the rescue. The need to accept several subwords per input word and to go through an intermediate alphabet and transducer makes them very complex. Even trivial languages such as a∗ require extra letters and checks in order to be recognized. Simplicity is less crucial in the process of automatic algorithms, and indeed, data automata have been succesfully used for the decidability of two-variable Variable Automata over Infinite Alphabets 3 first order logic on words with data - a formalism that is very useful in XML reasoning [2, 1]. For the purpose of specification and design, and for developing new algorithms and applications, simplicity is crucial. A simpler, friendlier formalism is needed.

Data and register automata and most of their variants fail the compositionality and computability criteria too. Data automata and register automata are not closed under complementation, apart from specific fragments of register automata that limit the number of registers [8]. Their universality and containment problems are undecidable [12].

Pebble automata and most of their variants fail the computability criterion, as apart from weaker models [14], their nonemptiness, universality, and containment problems are undecidable. Nonemptiness of data and register automata is decidable, but is far more complex than the easy reachability-based nonemptiness algorithm for NFAs.

We introduce and study a new formalism for recognizing languages over infinite alphabets. Our formalism, variable finite automata (VFA), forms a natural and simple extension of NFAs. We also identify and study a fragment of VFA that fulfills the simplicity, compositionality, and computability criteria, and is still sufficiently expressive to specify many interesting properties. Intuitively, a VFA is an NFA some of whose letters are variables ranging over the infinite alphabet. The tight connection with NFAs enables us to apply much of the constructions and algorithms known for them.

More formally, a VFA is a pair A = Σ, A, where Σ is an infinite alphabet and A is an NFA, referred to as the pattern automaton of A. The alphabet of A consists of constant letters – a finite subset of Σ, a set of bounded variables, and a single free variable. The language of A consists of words in Σ ∗ that are formed by assigning letters in Σ to the occurrences of variables in words in the language of A. Each bounded variable is assigned a different letter (also different from the constant letters), thus all occurrences of a particular bounded variable must be assigned the same letter. This allows describing words in Σ ∗ in which some letter is repeated. The free variable may be assigned different letters in every occurrence, different from the constant letters and from letters assigned to the bounded variables. This allows describing words in which every letter may appear. For example, consider a VFA A = N, A, where A has a bounded variable x and its free variable is y. if the language of A is (x + y)∗ · x · (x + y)∗ · x · (x + y)∗, then the language of A consists of all words over N in which at least some letter occurs at least twice.

We prove that VFAs are closed under union and intersection. The constructions we present use the union and product constructions for NFAs in their basis, but some pirouettes are needed in order to solve conflicts between different assignments to the variables of the underlying automata. Such pirouettes are helpless for the problem of complementation, and we prove that VFAs are not closed under complementation. We study the classical decision problems for VFAs. We show that a VFA is nonempty iff its pattern automaton is nonempty. Thus, the nonemptiness problem is NL-complete, and is not more complex than the one for NFAs. We also show that the membership problem is NP-complete. Thus, while the problem is more complex than the one for NFAs, it is still decidable. The universality and containment problems, however, are undecidable.

We then define and study deterministic VFA (DVFA), a fragment of VFA in which there exists exactly one run on every word. Unlike the case of DFAs, determinism is not a syntactic property. Indeed, since the variables are not pre-assigned, there may be 4 O. Grumberg, O. Kupferman, and S. Sheinvald several runs on a word even when the pattern automaton is deterministic. However, a syntactic definition does exist and deciding whether a given VFA is deterministic is NLcomplete. We introduce an unwinding operator for VFAs. In an unwinded VFA, each state is labeled by the variables that have been read, and therefore assigned, in paths leading to the state. Using the unwinding operator, we can define DVFAs for the union and intersection of DVFAs. Moreover, the closure under complementation of DVFAs is immediate, and it enables us to solve the universality and containment problems for DVFAs. Thus, DVFAs suggest an expressive formalism that fulfills the three criteria.

We study further properties of DVFA. As bad news, we show that the problem of determinizing a given VFA (or concluding that no equivalent DVFA exists) is undecidable. As good news, we show that all VFAs with no free variable have an equivalent DVFA, and present a determinization process for VFAs of this kind. The advantages of DVFA make us optimistic about the extensions of algorithms that involve DFAs, like symbolic formal verification and synthesis, to the setting of infinite alphabets.

We demonstrate the robustness of our formalism by showing that its extension to the setting of ω-regular words is straightforward. In Section 5, we introduce and study variable B¨ chi automata (VBAs), whose pattern automata are nondeterministic B¨ chi u u automata on infinite words [6]. VBAs are useful for specifying languages of infinite words over infinite alphabets, and in particular, specifications of systems with variables ranging over infinite domains. We show that the known relation between NFAs and nondeterministic B¨ chi automata extends to a relation between VFAs and VBAs. This u enables us to easily lift the properties and decision procedures we presented for VFA to the setting of VBAs.

2 Variable Automata over Infinite Alphabets

A nondeterministic finite automaton (NFA) is a tuple A = Γ, Q, Q0, δ, F, where Γ is a finite alphabet, Q is a finite set of states, Q0 ⊆ Q is a set of initial states, δ : Q × Γ → 2Q is a transition function, and F ⊆ Q is a set of accepting states. If there exists q such that q ∈ δ(q, a), we say that a exits q. A run of A on w = σ1 σ2... σn in Γ ∗ is a sequence of states r = r0, r1,..., rn such that r0 ∈ Q0 and for every 1 ≤ i ≤ n it holds that ri ∈ δ(ri−1, σi ). If rn ∈ F then r is accepting. Note that a run may not exist. If a run does exist, we say that w is read along A. The language of A, denoted L(A), is the set of words on which there exists an accepting run of A.

Before defining variable automata with infinite alphabets, let us explain the idea behind them. Consider the NFA A1 over the finite alphabet {x, y} appearing in Figure 1.

It is easy to see that L(A1 ) = x · y ∗ · x. Consider the language L = {i1 · i2 · · · ik :

k ≥ 2, i1 = ik, and ij = i1 for all 1 j k} over the alphabet N; that is, L contains exactly all words in which the first letter is equal to the last letter, and is different from all other letters. Since N is infinite, an NFW for it needs infinitely many states and transitions. The idea behind variable automata is to label the transitions of the NFA by both letters from the infinite alphabet and variables that can take values from it. For example, if we refer to x as a bounded variable whose value is fixed once assigned, and refer to y as a free variable, which can take changing values, different from the value assigned to x, then the NFA A1, when viewed as a variable automaton over N, Variable Automata over Infinite Alphabets 5

–  –  –

legal instance of v. Note that v may be the witnessing pattern for infinitely many words in Σ ∗, and that a word in Σ ∗ may have several witnessing patterns (or have none).

Given a word w ∈ Σ ∗, a run of A on w is a run of A on a witnessing pattern for w.

Pages:   || 2 | 3 |

Similar works:

«PREDICTION OF DELAM INATION IN WIND TURBINE BLADE STRU CTURAL DETA ILS John F. M andell, Douglas S. Cairns Daniel D. Samborsky, Robert B. Morehead and Darrin J. Haugen Montana State University Bozeman, Montana 59717 ABSTRACT Delamination between plies is the roo t cause of many failures o f composite materials structures such as wind turbine blades. Design methodologies to prevent such failures have not been widely available for the materials and processes used in blades. This paper presents...»

«Empirical study reveals deficits in the choice of formwork Michael Kapp ETH Zurich, Zurich, Switzerland (email: michael.kapp@ethz.ch) Gerhard Girmscheid ETH Zurich, Zurich, Switzerland (email: girmscheid@ibb.baug.ethz.ch) Abstract The choice of suitable construction techniques and methods must be made prior to construction commencing. Since sufficiently detailed plans are frequently not available at such an early phase, this decision – which significantly impacts the subsequent construction...»

«A Practical Technique for Improving the Accuracy of Interviewer Observations: Evidence from the National Survey of Family Growth Brady T. West Michigan Program in Survey Methodology bwest@umich.edu NSFG Survey Methodology Working Papers, No. 10013 November 2010 Practical Technique for Improving the Accuracy of Interviewer Observations 2 ABSTRACT Ideal auxiliary variables for use in post-survey nonresponse adjustments are associated with both survey variables of interest and response propensity....»

«Doesn’t Carbon-14 Dating Disprove the bible? Mike riddle S cientists use a technique called radiometric dating to estimate the ages of rocks, fossils, and the earth. Many people have been led to believe that radiometric dating methods have proved the earth to be billions of years old. This has caused many in the church to reevaluate the biblical creation account, specifically the meaning of the word “day” in Genesis chapter  and its length. With our focus on one particular form of...»

«Domain-Independent Support for Computer-Based Education of Argumentation Skills Doctoral Thesis (D i s s e r t a t i o n) to be awared the degree Doctor rerum naturalium (Dr. rer. nat.) submitted by Frank Loll from Burgwedel approved by the Faculty of Mathematics/Computer Science and Mechanical Engineering, Clausthal University of Technology Date of oral examination February 14th, 2012 Chairperson of the Board of Examiners Prof. Dr. Jörg P. Müller Chief Reviewer Prof. Dr. Niels Pinkwart...»

«BD Buoyancy Compensator User's Manual 2 BD BUOYANCY COMPENSATOR USER'S MANUAL Copyright NotiCe This owner’s manual is copyrighted, all rights reserved. It may not, in whole or in part, be copied, photocopied, reproduced, translated, or reduced to any electronic medium or machine readable form with out prior consent in writing from Aqua Lung America, Inc. ©2013 Aqua Lung international BD User’s Manual p/N 18407 you can contact a technical Advisor via e-mail at: rbedard@aqualung.com...»

«Doubling Down Jonathan Rhinesmith* June 7, 2014 Abstract I demonstrate that when investment fund managers “double down” on positions that have run against them, they outperform. Specifically, I find that a portfolio formed of the U.S. equity positions that hedge fund managers add to after recent stock-level underperformance generates significant annualized risk-adjusted outperformance of between 5% and 15%. This finding is not the result of a simple reversal effect, of a fund’s best...»

«Preprint of: Williams, Virginia Kay, and Schmidt, June. (2008). Determining the Average Cost of a Book for Allocation Formulas: Comparing Options. Library Resources & Technical Services 52(1): 60-70. Note: This pre-print is not an exact representation of the published paper. Tables and figures appear at the end of the text and minor revisions may have been made. Determining the Average Cost of a Book for Allocation Formulas: Comparing Options Virginia Kay Williams Assistant Collection...»

«Seminar R&D Nuclear Malaysia 2012 (RnD12), Dewan Tun Dr. Ismail, Agensi Nuklear Malaysia, 26-28 September 2012 NATURAL RADIOACTIVITY CONTENT AND RADIONUCLIDES LECHABILITY OF BRICKS CONTAINING INDUSTRIAL WASTE Zalina Laili, Mohd Zaidi Ibrahim, Nur Azna Mahmud and Muhamat Omar Waste & Environmental Technology Division, Malaysian Nuclear Agency (Nuclear Malaysia), Bangi, 43000 Kajang, Selangor D.E., Malaysia *E-mail :liena@nuclearmalaysia.gov.my Abstract A study have been carried out using...»

«Dave Wolstencroft Technical Manager 4B Components HOW STEEL WEB ELEVATOR BELT & SJ BUCKETS ENHANCE THE PERFORMANCE OF BUCKET ELEVATORS Introduction With the demand for larger capacities, for more efficient and cost effective elevators to carry industrial products such as cement, 4B Components has researched, tested and supplied the industry for over the last nine years with an integrated system of steel web belting, SJ buckets and elevator designs for compact industrial elevators. 4B Components...»

«The transformation of Fe(III) oxides catalysed by Fe2+ and the fate of arsenate during transformation and reduction of Fe(III) oxides Hanne Dahl Pedersen Institute of Environment & Resources The transformation of Fe(III) oxides catalysed by Fe2+ and the fate of arsenate during transformation and reduction of Fe(III) oxides Hanne Dahl Pedersen Ph.D. Thesis February 2006 Institute of Environment & Resources Technical University of Denmark The transformation of Fe(III) oxides catalysed by Fe2+ and...»

«CASSY Lab 2 CASSY Lab 2 524 221en © by LD DIDACTIC GmbH · Leyboldstrasse 1 · D-50354 Huerth · www.ld-didactic.com Phone: +49-2233-604-0 · Fax: +49-2233-604-222 · E-mail: info@ld-didactic.de · Technical alterations reserved CASSY Lab 2 Copyright School license (524 220) The activated software may only be used by the purchaser and solely for the purpose of instruction in the respective educational institution. This includes lessons prepared at home. You may not reveal your activation code...»

<<  HOME   |    CONTACTS
2016 www.thesis.xlibx.info - Thesis, documentation, books

Materials of this site are available for review, all rights belong to their respective owners.
If you do not agree with the fact that your material is placed on this site, please, email us, we will within 1-2 business days delete him.