A power-set construction for reducing Büchi automata to non-determinism degree two

Büchi automata are finite automata that accept languages of infinitely long strings, so-called ω-languages. It is well known that, unlike in the finite-string case, deterministic and non-deterministic Büchi automata accept different ω-language classes, i.e., that determination of a non-deterministic Büchi automaton using the classical power-set construction will yield in general a deterministic Büchi automaton which accepts a superset of the ω-language accepted by the given non-deterministic automaton.In this paper, a power-set construction to a given Büchi automaton is presented, which reduces the degree of non-determinism of the automaton to at most two, meaning that to each state and input symbol, there exist at most two distinct successor states. The constructed Büchi automaton of non-determinism degree two and the given Büchi automaton of arbitrary non-determinism degree will accept the same ω-language.     

ω-Computations on Turing machines

The paper develops the theory of Turing machines as recognizers of infinite (ω-type) input tapes. Various models of ω-type Turing acceptors are considered, varying mainly in their mechanism for recognizing ω-tapes. A comparative study of the models is made. It is shown that regardless of the ω-recognition model considered, non-deterministic ω-Turing acceptors are strictly more powerful than their deterministic counterparts. Canonical forms are obtained for each of the ω-Turing acceptor models. The corresponding families of ω-sets are studied; normal forms and algebraic characterizations are derived for each family.     

Characterization of ω-regular languages by first-order formulas

First-order formulas are used to specify various ways of acceptance of ω-languages by (deterministic) finite automata, and we study the relationship between the ‘arithmetic’ hierarchy of the formulas in prenex normal form and the topological hierarchy of the accepted ω-languages. Among other things it is proved that the ω-languages accepted by finite automata under the accepting conditions specified by Σ₁-type formulas are precisely open ω-regular languages, those accepted under the conditions specified by Σ₂-type formulas coincide with the ω-regular languages which are denumerable unions of closed sets, and that as long as the accepting conditions are specified by first-order formulas the accepted ω-languages remain to be ω-regular.     

A hierarchy of deterministic context-free ω-languages

Twenty years ago, Klaus. W. Wagner came up with a hierarchy of ω-regular sets that actually bears his name. It turned out to be exactly the Wadge hierarchy of the sets of ω-words recognized by deterministic finite automata. We describe the Wadge hierarchy of context-free ω-languages, which stands as an extension of Wagner's work from automata to pushdown automata.     

Infinitary tree languages recognized by ω-automata

We define top-down infinite tree automata (ω-automata) which is an extension of Rabin's automata to infinite Σ-tress. We prove that each ω-automaton can be completed to an equivalent one and that non-deterministic ω-automata have more power than deterministic ω-automata. We study the difference between ω-languages and deterministic ω-languages by using AFL-like operations.     

Complexity of Boolean algebras

We show that the elementary theory of Boolean algebras is _log-complete for the Berman complexity class _c<ω STA(*, 2^cn, n), the class of sets accepted by alternating Turing machines running in time 2^cn for some constant c and making at most n alternations on inputs of length n; thus the theory is computationally equivalent to the theory of real addition with order. We extend the completeness results to various subclasses of Boolean algebras, including the finite, free, atomic, atomless, and complete Boolean algebras. Finally we show that the theory of any finite collection of finite Boolean algebras is complete for PSPACE, while the theory of any other collection is _log-hard for _c<ω STA(*, 2^cn, n).     

Spatially referenced methods of processing raster and vector data

The authors consider a general method of constructing addressing and arithmetic systems for two-dimensional image data using the hierarchy of ‘molecular’ tilings based on an original isohedral ‘atomic’ tiling. (Each molecular title at level k is formed from a constant number of tiles at level k−1; this is termed the ‘aperture’ property of the hierarchy.) In addition they present 11 objective criteria (which are of significance in cartographic image processing), by which these hierarchies and tilings may be described and compared.

Of the 11 topologically distinct types of isohedral tiling, three ([3⁶], [4⁴] and [6³]) are composed of regular polygons, and two of these ([3⁶] and[4⁴]) satisfy the condition that all tiles have the same ‘orientation’. In general, although each level in a hierarchy is topologically equivalent, the tiles may differ in shape at different levels and only [6³], [4⁴], [4.8²] and [4.6.12] are capable of giving rise to hierarchies in which the tiles at all levels are the same shape. The possible apertures of hierarchies obeying this condition are n² (for any n > 1)in the cases of [6³] and [4⁴]; n² or 2n² in the case of [4.8²]; and n² or 3n² in the case of [4.6.12].

In contrast the only tiling exhibiting the uniform ‘adjacency’ criterion is[3⁶]. However, hierarchies based on this atomic tiling generate molecular tiles with different shapes at every level. If these disadvantages are accepted, hierarchies based on first-level molecular tiles referred to as the 4-shape, 4′-shape, 7-shape and 9-shape are generated. Of these the 4-shape and the 9-shape appear to satisfy many of the cartographically desirable properties in addition to having an atomic tiling which exhibits uniform adjacency.

In recent years the generalized balanced ternary addressing system has been developed to exploit the image processing power of the 7-shape. The authors have generalized and extended this system as ‘tesseral addressing and arithmetic’, showing how it can be used to render a 4-shape into a spatially correct linear quadtree.     

An Abstract Böhm-normalization

We study normalization by neededness with respect to ‘infinite results’, such as Böhm-trees, in an abstract framework of Stable Deterministic Residual Structures. We formalize the concept of ‘infinite results’ for finite terms as suitable sets of infinite reductions, and prove an abstract infinitary normalization theorem with respect to such sets. We also give a sufficient and necessary condition for existence of minimal normalizing reductions.     

Independence results about context-free languages and lower bounds

We show that for any axiomatizable, sound formal system F there exist instances of natural problems about context-free languages, lower bounds of computations and P versus NP that are not provable in F for any recursive representation of these problems. Most previous independence results in computer science have been proven for specific representations of the problems, by exploiting the ‘opaqueness’ of Turing machine names. Our results rely on the complexity of the logical structure of the problem and yield independence results which do not depend on the representations of problems. We show, for example, that there exists a nonregular context-free language L₀ such that for no cf-grammar G, L(G) = L₀, it is provable in F that “L(G) is not regular”. We also show, among other results about P and NP, that there exists a recursive oracle A such that NP^A ≠ P^A, and that this fact is not provable in F for any recursive representation of A.

The difference of what is and is not provable in F is well illustrated by questions about polynomial time isomorphisms (p-isomorphisms) of NP-complete sets. We show that for every NP-complete set, L, there is a representation of L by a nondeterministic polynomial time machine for which we can prove that L is NP-complete. Furthermore, if L is p-isomorphic to SAT, then this is also provable in F for some representation of L. On the other hand, if there exist NP-complete sets not p-isomorphic to SAT, then there exists an NP-complete set L for which, independent of its representation, there is no proof in F that L is or is not p-isomorphic to SAT.     

Computational complexity via programming languages: constant factors do matter

The purpose of this work is to promote a programming-language approach to studying computability and complexity, with an emphasis on time complexity. The essence of the approach is: a programming language, with semantics and complexity measure, can serve as a computational model that has several advantages over the currently popular models and in particular the Turing machine. An obvious advantage is a stronger relevance to the practice of programming. In this paper we demonstrate other advantages: certain proofs and constructions that are hard to do precisely and clearly with Turing machines become clearer and easier in our approach, and sometimes lead to finer results. In particular, we prove several time hierarchy theorems, for deterministic and non-deterministic time complexity which show that, in contrast with Turing machines, constant factors do matter in this framework. This feature, too, brings the theory closer to practical considerations. The above result suggests that this framework may be appropriate for studying low complexity classes, such as linear time. As an example we give a problem complete for non-deterministic\/ linear time under deterministic linear-time reductions. Finally, we consider some extensions and modifications of our programming language and their effect on time complexity results. Received: 26 October 1998 / 9 June 2000     

A simulation method for time-dependent structural reliability

A one-dimensional simulation procedure is developed for use in estimating structural reliability in multi-dimensional load and resistance space with the loads represented as stochastic process. The technique employed is based on the idea of using ‘strips’ of points parallel to each other and sampled on the limit state hyperplanes. The ‘local’ outcrossing rate and the zero time failure probability P_f(0) associated with the narrow strips are derived using the conditional reliability index. When the domain boundary consists of a set of limit states, second order bounds are used to obtain a lower bound approximation of the outcrossing rate and P_f(0) associated with the union of a set of λ strips. It is shown by examples that for high reliability problems, λ may be much less than the number of limit states without significant loss of accuracy and with considerable saving in computation time. It was also found that the rate of convergence of the simulations is quite fast even without using importance sampling.     

The living in a lattice rule language

This paper presents a rule-based query language for an object-oriented database model. The database model supports complex objects, object identity, classes and types, and a class/type hierarchy. The instances are described by ‘object relations’ which are functions from a set of objects to value sets and other object sets. The rule language is based on object-terms which provide access to objects via the class hierarchy. Rules are divided into two classes: object-preserving rules manipulating existing objects (yielding a new ‘view’ on objects available in the object base) and object-generating rules creating new objects with properties derived from existing objects. The derived object sets are included in a class lattice. We give conditions for whether the instances of the ‘rules’ heads are ‘consistent’, i.e. represent object relations where the properties of the derived objects are functionally determined by the objects.     

McClellan transformation and the construction of biorthogonal wavelet bases of LR

Bidimensional wavelet bases are constructed by means of McClellan's transformation applied to a pair of one-dimensional biorthogonal wavelet filters. It is shown that under some conditions on the transfer function F(ω₁,ω₂) associated to the McClellan transformation and on the dilation matrix D, it is possible to construct symmetric compactly supported biorthogonal wavelet bases of L²(R²). Finally, the construction method is illustrated by means of numerical examples.     

Turing machines with access to history

We study remembering Turing machines, that is Turing machines with the capability to access freely the history of their computations. These devices can detect in one step via the oracle mechanism whether the storage tapes have exactly the same contents at the moment of inquiry as at some past moment in the computation. The s(n)-space-bounded remembering Turing machines are shown to be able to recognize exactly the languages in the time-complexity class determined by bounds exponential in s(n). This is proved for deterministic, non-deterministic, and alternating Turing machines.     

Expressive power of first-order recurrent neural networks determined by their attractor dynamics

We provide a characterization of the expressive powers of several models of deterministic and nondeterministic first-order recurrent neural networks according to their attractor dynamics. The expressive power of neural nets is expressed as the topological complexity of their underlying neural ω-languages, and refers to the ability of the networks to perform more or less complicated classification tasks via the manifestation of specific attractor dynamics. In this context, we prove that most neural models under consideration are strictly more powerful than Muller Turing machines. These results provide new insights into the computational capabilities of recurrent neural networks.     

Some issues of structure and control for linear time-invariant systems

The objective of this paper is to emphasise the role played by particular structures in the solution of some control problems. The so-called “structural approach” relies on various indicators of dynamical systems such as, for instance, finite and infinite zeros, kernel indices, …. The fundamental invariance properties of these structures under the action of some transformations groups (e.g. feedback) are at the origin of their key role. Structural solutions to “classical” control problems, such as disturbance rejection, model matching and non-interaction are now rather well known: zeros at infinity play a role in the existence of “proper” solutions, while finite (invariant) zeros allow for the characterisation of “fixed poles”, whose location in the complex plane gives answer to pole placement limitations (including stability). Among the recent contributions to this structural approach, a particular attention is here devoted to:

- “Partial” versions of some of these control problems: The control objective only concerns a finite number of (and not necessarily all) the first Markov parameters of the transfer function matrix of the controlled system (e.g. to be zero for disturbance rejection or model matching, to be diagonal for non-interaction). Some interesting new issues in the dual context of failure detection are also sketched.

- Generalised solutions: Based on proportional and derivative feedback laws, with new issues in the context of systems with variable internal structures, and also for systems with delays.

Geometric concepts, such as invariant and almost invariant subspaces, and algebraic counterparts, such as factorisations on some special rings, are intermediary tools which support the characterisations of those particular structures and which allow for a structural treatment of the considered control and/or observation problems.

The results are here presented without proof: references are given to previous published results (in most cases in books and journals which are easily available), and some simple examples are used to illustrate non-standard notions (among which systems with variable internal structure, and time domain left invertibility).

Most of the results here presented rely on long and intensive collaborations between the author and various colleagues.     

A practical procedure for conceptual design and testing of machine tool structure

This paper discusses the initial development of a machine tool and its structure (concept, calculation, design) and the verification of the prototype. The topics studied include two issues: static rigidity and dynamic stability. For static rigidity several experiments and modelling studies using the finite element method have been carried out in order to identify the model parameters. In this way differences between models of bolted joints, slideways and the cross-section of the structural elements have been determined. The model is formed by design documentation and later verified through experiments on the prototype of the machine. The approach is different in the case of dynamic stability. The model is not made on the basis of design documentation or static calculations, but by experiments performed on the prototype. This relates to an oriented transfer function; parameters are determined by fitting experimental transfer function curves. With this model, the stability is analyzed under different machining conditions. Specific features of this methodology are as follows:

• • The finite element method is used for qualitative comparison of different machine tool structure concepts during the conceptual and design stages. Only after completion of the prototype may the parameters of the prototype model be adjusted for the purpose of obtaining quantitative indicators.

• • Dynamics are analyzed by parameter identification of the oriented transfer function model. The dominant degree of freedom is naturally selected by experiment and not from hypotheses about the behavior of structures obtained from mathematical manipulations such as expansion of the model according to the finite element method. If necessary another machine tool structure may be modelled; in this way hypotheses are drawn about the stability of the reconstructed prototype.

Such a procedure has been applied and verified on the machine tool structure of a horizontal machining center. Results for static rigidity and dynamic stability have been obtained from the model and experiments performed on the prototype. The following techniques have been used:

• • finite element method for qualitative identification of static behavior,

• • self-excitation of the machine,

• • digital signal processing on the FFT basis,

• • smoothing of curves and digital filtration,

• • function fitting of the transfer function (modal analysis),

• • coefficient calculus and oriented transfer function,

• • stability assessment of the fitted model under different machining conditions, and

• • modelling of the regenerative machining effect by cutting.

Necessary tests have been done by instruments required for the use of the above techniques.

Such a combined static-dynamic criteria procedure for structuring a machine tool enables efficient follow-up of all results and facilitates necessary future expansion, the utilization of universal equipment, the combination of modelling and experiments, and the synthesis of simple models of the examined machine with behavior identical to the machine. The well-known machining system dynamic stability theories are applied to such models.     

Continuous exposure to noisy work environments does affect preferred leisure noise levels

Although noise research concentrates principally on the workplace, recent studies have shown that preferred leisure noise may be as loud as 10 dBA higher than workplace levels. This two-phase study compared leisure noise preferences for workers who were exposed to either a ‘loud’ (≥ 85 dBA) or ‘not loud’ (< 85 dBA) work environment. Phase 1 examined 110 subjects' noise level preferences that were recorded before and after work for a one-day observation. Phase 2 recorded 12 additional subjects' preferences for five consecutive days. Analysis of both phases' results determined that leisure noise levels prior to work were not significantly different. Those exposed to the ‘loud’ environment preferred noise levels significantly higher (6.5 to 9 dBA) than their before work levels. Over the five consecutive days (Phase 2) only the ‘loud’ group preferred noise levels significantly higher after work (Day 5 versus Day 1). Thus, it can be concluded that ‘loud’ work environments and consecutive daily exposure to these environments do influence preferred leisure noise levels.