Linking theorems for tree transducers

Linear extended multi bottom-up tree transducers are presented in the framework of synchronous grammars, in which the input and the output tree develop in parallel by rewriting linked nonterminals (or states). These links are typically transient and disappear once the linked nonterminals are rewritten. They are promoted to primary objects here, preserved in the semantics, and carefully studied. It is demonstrated that the links computed during the derivation of an input and output tree pair are hierarchically organized and that the distance between (input and output) link targets is bounded. Based on these properties, two linking theorems are developed that postulate the existence of certain natural links in each derivation for a given input and output tree pair. These linking theorems allow easy, high-level proofs that certain tree translations cannot be implemented by (compositions of) linear extended multi bottom-up tree transducers.     

Complementing two-way finite automata

We study the relationship between the sizes of two-way finite automata accepting a language and its complement. In the deterministic case, for a given automaton (2dfa) with n states, we build an automaton accepting the complement with at most 4n states, independently of the size of the input alphabet. Actually, we show a stronger result, by presenting an equivalent 4n-state 2dfa that always halts. For the nondeterministic case, using a variant of inductive counting, we show that the complement of a unary language, accepted by an n-state two-way automaton (2nfa), can be accepted by an O(n⁸)-state 2nfa. Here we also make 2nfa’s halting. This allows the simulation of unary 2nfa’s by probabilistic Las Vegas two-way automata with O(n⁸) states.     

Group weighted finite transducers

We consider weighted finite transducers over arbitrary groups, that is finite transducers having a counter in which, at any step, a value of the group is stored but no information regarding the content of this counter is available until the computation is finished. The computation is valid if the counter value is the neutral element of the group. We generalize here some results from [8] and [17]. Received: 28 January 2001 / 5 June 2001     

Characterization theorems on abstract families of transducers

For an AFL /oL and an AFT /oM, /oM(/oL) denotes the family of languages obtained from languages in /oL by imposing transformations through transducers in /oM. Then /oM (/oL) is a full AFL. Two characterization theorems of /oM (/oL) are given. One is in terms of homomorphism and intersection, and the other is in terms of AFA with control set.     

Multihead two-way probabilistic finite automata

We present properties of multihead two-way probabilistic finite automata that parallel those of their deterministic and nondeterministic counterparts. We define multihead probabilistic finite automata withlogspace constructible transition probabilities, and we describe a technique to simulate these automata by standard logspace probabilistic Turing machines. Next, we represent logspace probabilistic complexity classes as proper hierarchies based on corresponding multihead two-way probabilistic finite automata, and we show their (deterministic logspace) reducibility to the second levels of these hierarchies. We obtain a simple formula for the maximum inherent bandwidth of the configuration transition matrices associated with thek-head probabilistic finite automata processing a length-n input string. (The inherent bandwidth of the configuration transition matrices associated with an automaton processing a length-n input string is the smallest bandwidth we can get by changing the enumeration order of the automaton’s configurations.) Partially based on this relation, we find an apparently easier logspace complete problem forPL (the class of languages recognized by logspace unbounded-error probabilistic Turing machines), and we discuss possibilities for a space-efficient deterministic simulation of probabilistic automata.     

On the valuedness of finite transducers

Summary We investigate the valuedness of finite transducers in connection with their inner structure. We show: The valuedness of a finite-valued nondeterministic generalized sequential machine (NGSM) M with n states and output alphabet is at most the maximum of (1-1/#) · (2 ^k ₁ · k ₃ ) ⁿ · n ⁿ ·# ^{n 3 ·k} ₄ / ³ and 1/#·(2 ^k ₂ ·k ₃ ·(1+k ₄ )) ⁿ ·n ⁿ where k ₁6.25 and k ₂11.89 are constants and k ₃1 and k ₄0 are local structural parameters of M. There are two simple criteria which characterize the infinite valuedness of an NGSM. By these criteria, it is decidable in polynomial time whether or not an NGSM is infinite-valued. In both cases, # > 1 and # = 1, the above upper bound for the valuedness is almost optimal. By reduction, all results can be easily generalized to normalized finite transducers.     

The theorems of geometric variation for nonlinear finite element analysis

This paper illustrates the application of the theorems of geometric variation to the reanalysis of nonlinear finite element structures. The formulations presented here are compared for efficiency with the Newton-Raphson methods for a number of problems. This comparison indicates the efficiency of the proposed techniques and the type of problems where the techniques may be used profitably.     

Some algebraic properties of measure-once two-way quantum finite automata

Quantum finite automata (QFA) can be divided into four kinds depend upon the head-directions and the measure times. They are measure-once one way QFA (MO-1QFA) introduced by Moore and Crutchfield (Theor Comput Sci 237: 275–306, 2000); measure-many one way QFA (MM-1QFA) and measure-many two-way QFA (MM-2QFA) introduced by Kondacs and Watrous (Proceedings of the 38th IEEE annual symposium on 433 foundations of computer science, 66–75, 1997); and measure-once two-way QFA (MO-2QFA) which were not given until now. The purpose of this work is mainly to discuss one kind of QFA, which is called MO-2QFA for brief. First of all, the definition of MO-2QFA is given and the conditions for preserving unitary properties are shown. Then, we analysis the basic algebraic properties of the class of languages which can be recognized by MO-2QFA, such as the union, intersection, complement and reversal operations. As well, we consider the catenation operation on the class of quantum languages recognized by MO-2QFA is closed in the generalized conditions.      

Synthesis of finite state machines for improved state verification

Finite State Machines (FSMs) are used in diverse areas to model hardware and software systems. Verification of FSMs is essential to ensure reliability of systems. To verify that a machine is in an expected state in testing, Unique Input/Output (UIO) sequences are used. The aforementioned testing methodology requires that each state in the FSM has an UIO. However, it is possible for a given machine that few or even none of its states have an UIO sequence. This paper presents a guided heuristic algorithm for synthesizing FSMs such that each state has an UIO sequence. The states of an FSM with identical I/O labels on transitions are grouped in order to identify the states which do not possess UIO sequence. The transitions are then augmented by adding extra output terminals incrementally so that new UIO sequences are created for the states. A greedy approach is used to optimize the number of added outputs. Initially, the transitions which lead to state convergence (i.e., transitions with identical input/output labels taking a set of states to the same next state) and constrained self-loop (i.e., transitions taking a set of states either to itself or leads to state convergence) are identified since a state with only these transitions will never have a UIO sequence. Extra output terminals are added to the FSM which are used only while testing and the augmented output labels make sure that the states are neither convergent nor has constrained self-loop, thereby ensuring UIO sequence. The proposed algorithm, referred to as AUGP, was tested with a large number of FSMs including the Microelectronics Center of North Carolina (MCNC) FSM benchmarks. The augmented state transition table was used as input to a UIO computation algorithm (developed by the same authors [Ahmad I, et al. IEE Proc Comput Digital Tech 2004;151(2):131]) to check the performance of the augmentation algorithm and the tested FSMs were found to possess UIO sequence for all states.     

Canonical finite state machines for distributed systems

There has been much interest in testing from finite state machines (FSMs) as a result of their suitability for modelling or specifying state-based systems. Where there are multiple ports/interfaces a multi-port FSM is used and in testing, a tester is placed at each port. If the testers cannot communicate with one another directly and there is no global clock then we are testing in the distributed test architecture. It is known that the use of the distributed test architecture can affect the power of testing and recent work has characterised this in terms of local s-equivalence: in the distributed test architecture we can distinguish two FSMs, such as an implementation and a specification, if and only if they are not locally s-equivalent. However, there may be many FSMs that are locally s-equivalent to a given FSM and the nature of these FSMs has not been explored. This paper examines the set of FSMs that are locally s-equivalent to a given FSM M. It shows that there is a unique smallest FSM χ_min(M) and a unique largest FSM χ_max(M) that are locally s-equivalent to M. Here smallest and largest refer to the set of traces defined by an FSM and thus to its semantics. We also show that for a given FSM M the set of FSMs that are locally s-equivalent to M defines a bounded lattice. Finally, we define an FSM that, amongst all FSMs locally s-equivalent to M, has fewest states. We thus give three alternative canonical FSMs that are locally s-equivalent to an FSM M: one that defines the smallest set of traces, one that defines the largest set of traces, and one with fewest states. All three provide valuable information and the first two can be produced in time that is polynomial in terms of the number of states of M. We prove that the problem of finding an s-equivalent FSM with fewest states is NP-hard in general but can be solved in polynomial time for the special case where there are two ports.     

Active learning for extended finite state machines

We present a black-box active learning algorithm for inferring extended finite state machines (EFSM)s by dynamic black-box analysis. EFSMs can be used to model both data flow and control behavior of software and hardware components. Different dialects of EFSMs are widely used in tools for model-based software development, verification, and testing. Our algorithm infers a class of EFSMs called register automata. Register automata have a finite control structure, extended with variables (registers), assignments, and guards. Our algorithm is parameterized on a particular theory, i.e., a set of operations and tests on the data domain that can be used in guards.Key to our learning technique is a novel learning model based on so-called tree queries. The learning algorithm uses tree queries to infer symbolic data constraints on parameters, e.g., sequence numbers, time stamps, identifiers, or even simple arithmetic. We describe sufficient conditions for the properties that the symbolic constraints provided by a tree query in general must have to be usable in our learning model. We also show that, under these conditions, our framework induces a generalization of the classical Nerode equivalence and canonical automata construction to the symbolic setting. We have evaluated our algorithm in a black-box scenario, where tree queries are realized through (black-box) testing. Our case studies include connection establishment in TCP and a priority queue from the Java Class Library.