In this part of the present text, we reach a third level of abstraction. Recall that in Part I relations were observed as they occur in real life situations. We then made a step forward using point-free algebraic formulation in Part II; however, we did not introduce the respective algebraic proofs immediately. Instead, we visualized the effects and tried to construct with relations. In a sense, this corresponds to what one always finds in a book treating eigenvectors and eigenvalues of real- or complexvalued matrices, or their invariant subspaces: usually this is heavily supported with visualizing matrix situations. We did this with full mathematical rigor but have not yet convinced the reader concerning this fact. Proofs, although rather trivial in that beginning phase, have been postponed so as to establish an easy line of understanding first.

As gradually more advanced topics are handled, we will now switch to a fully formal style with proofs immediately appended. However, the reader will be in a position to refer to the first two parts and to see there the effects.

Formulating only in algebraic terms – or what comes close to that, formulating in the relational language TituRel – means that we are far more restricted in expressivity. On the other hand this will improve the precision considerably. Restricting ourselves to the relational language will later allow computer-aided transformations and proofs.

Ambiguity refers to the property whereby regular expressions or patterns have multiple matching possibilities. As discussed in Chapter 5, ambiguity can make the behavior of a program harder to understand and can actually be the result of a programming error. Therefore it is often useful to report it to the user. However, when we come to ask exactly what we mean by ambiguity, there is no consensus. In this chapter, we review three different definitions, strong ambiguity, weak ambiguities and binding ambiguity, and discuss how these notions are related to each other and how they can be checked algorithmically.

Caveat: In this chapter, we concentrate on regular expressions and patterns on strings rather than on trees in order to highlight the essence of ambiguity. The extension for the case of trees is routine and can be found in the literature.

Ambiguities for regular expressions

In this section, we study strong and weak ambiguities and how they can be decided by using an ambiguity checking algorithm for automata.

14.1.1 Definitions

Ambiguity arises when a regular expression has several occurrences of the same label. Therefore we need to be able to distinguish between these occurrences.

It has been shown in Chapters 2 and 3 how moderately sized sets (termed basesets when we want to stress that they are linearly ordered, non-empty, and finite), elements, vectors, and relations can be represented. There is a tendency to try to extend these techniques indiscriminately to all finite situations. We do not follow this trend. Instead, sets, elements, vectors, or relations – beyond those related to ground sets – will carefully be constructed, in particular if they are ‘larger’. Only a few generic techniques are necessary. They are presented here in detail as appropriate.

These techniques are far from being new. We have routinely applied them in an informal way since our school days. What is new in the approach chosen here is that we begin to take these techniques seriously: pair forming, if–then–else–fi–handling of variants, quotient forming, etc. For pairs, we routinely look for the first and second components; when a set is considered modulo an equivalence, we work with the corresponding equivalence classes and obey carefully the rule that our results should not depend on the specific representative chosen, etc.

What has been indicated here, however, requires a more detailed language to be expressed. This in turn means that a distinction between language and interpretation is suddenly important, which one would like to abstract from when handling relations ‘directly’. It turns out that only one or two generically defined relations are necessary for each construction step with quite simple and intuitive algebraic properties.

Concerning syntax and notation, everything is now available to work with. We take this opportunity to have a closer look at the algebraic laws of relation algebra. In particular, we will be interested in how they can be traced back to a small subset of rules which can serve as axioms. We present them now and discuss them immediately afterwards.

We should stress that we work with heterogeneous relations. This contrasts greatly with the traditional work of the relation algebra community which is almost completely restricted to a homogeneous environment – possibly enhanced by cylindric algebra considerations. Some of the constructs which follow simply do not exist in a homogeneous context, for example the direct power and the membership relation. At first glance, it seems simpler to study homogeneous as opposed to heterogeneous relations. But attempting domain constructions in the homogeneous setting immediately leads necessarily to non-finite models. Also deeper problems, such as the fact that ╥A,B; ╥B,C = ╥A,C does not necessarily hold, have only recently come to attention; this applies also to unsharpness.

Laws of relation algebra

The set of axioms for an abstract (possibly heterogeneous) relation algebra is nowadays generally agreed upon, and it is rather short. When we use the concept of a category, this does not mean that we are introducing a higher concept. Rather, it is used here as a mathematically acceptable way to prevent multiplying a 7 × 5-matrix with a 4 × 6-matrix.

After one's first work with orderings, one will certainly come across a situation in which the concept of an ordering cannot be applied in its initial form, a high jump competition, for example. Here certain heights are given and athletes achieve them or not. Often, more than one athlete will reach the same maximum height, for example a whole class of athletes will jump 2.35 m high. Such a situation can no longer be studied using an order – one will switch to a preorder. We develop the traditional hierarchy of orderings (linear strictorder, weakorder, semiorder, intervalorder) in a coherent and proof-economic way. Intervalorders are treated in more detail since they have attracted much attention in their relationship with interval graphs, transitive orientability, and the consecutive 1s property. Block-transitive strictorders are investigated as a new and algebraically promising concept. Then we study how an ordering of some type can – by slightly extending it – be embedded into some more restrictive type; for example, a semiorder into its weakorder closure.

In a very general way, equivalences are related to preorders, and these in turn are related to measurement theory as used in physics, psychology, economic sciences, and other fields. Scientists have contributed to measurement theory in order to give a firm basis to social sciences or behavioral sciences. The degree to which a science is considered an already developed one depends to a great extent on the ability to measure.

It is shown that the syntactic algebra of the characteristic series of a rational language L is semisimple in the following two cases: L is a free submonoid generated by a bifix code, or L is a cyclic language.

This chapter has two appendices, one on semisimple algebras (without proofs) and another on simple semigroups, with concise proofs. We use the symbols A1 and A2 to refer to them.

Bifix codes

Let E be a set of endomorphisms of a finite dimensional vector space V. Recall that E is called irreducible if there is no subspace of V other than 0 and V itself which is invariant under all endomorphisms in E. Similarly, we say that E is completely reducible if V is a direct sum V = V1 ⊕…⊕ Vk of subspaces such that for each i, the set of induced endomorphisms e∣Vi of Vi, for e ϵ E, is irreducible.

A set of matrices in Kn×n (K being a field) is irreducible (resp. completely reducible) if it is so, viewed as a set of endomorphisms acting at the right on K1×n, or equivalently at the left on Kn×1 (for this equivalence, see Exercises 1.1 and 1.2).

A linear representation (λ, μ, γ)ofaseries S ϵ K⟪A⟫ is irreducible (resp. completely reducible) if the set of matrices {μa ∣ a ϵ A}(or equivalently the sets μA* or μ(K⟨A⟩)) is so.

This chapter gives a presentation of results concerning the minimization of linear representations of recognizable series. A central concept of this study is the notion of syntactic algebra, which is introduced in Section 2.1. Rational series are characterized by the fact that their syntactic algebras are finite dimensional (Theorem 1.2). The syntactic right ideal leads to the notion of rank and of Hankel matrix; the quotient by this ideal is the analogue for series of the minimal automaton for languages.

Section 2.2 is devoted to the detailed study of minimal linear representations. The relations between representations and syntactic algebra are given. Two minimal representations are always similar (Theorem 2.4), and an explicit form of the minimal representation is given (Corollary 2.3).

The minimization algorithm is presented in Section 2.3. We start with a study of prefix sets. The main tool is a description of bases of right ideals of the ring of noncommutative polynomials (Theorem 3.2).

Several important consequences are given. Among them are Cohn's result on the freeness of right ideals, the Schreier formula for right ideals and linear recurrence relations for the coefficients of a rational series. A detailed description of the minimization algorithm completes the chapter.

Syntactic ideals

We start by assuming that K is a commutative ring. The algebra of polynomials K ⟨A⟩ is a free K-module having as a basis the free monoid A*. Consequently, the set K ⟪A⟫ of formal series can be identified with the dual of K⟨A⟩.