Volker Diekert

Anca Muscholl

Igor Walukiewicz

A Note on Monitors and Büchi automata

When a property needs to be checked against an unknown or very complex system, classical exploration techniques like modelchecking are not applicable anymore. Sometimes a monitor can be used, that checks a given property on the underlying system at runtime. A monitor for a property L is a deterministic finite automaton ML that after each finite execution tells whether (1) every possible extension of the execution is in L, or (2) every possible extension is in the complement of L, or neither (1) nor (2) holds. Moreover, L being monitorable means that it is always possible that in some future the monitor reaches (1) or (2). Classical examples for monitorable properties are safety and cosafety properties. On the other hand, deterministic liveness properties like "infinitely many a's" are not monitorable. We discuss various monitor constructions with a focus on deterministic !-regular languages. We locate a proper subclass of deterministic !regular languages but also strictly large than the subclass of languages which are deterministic and codeterministic; and for this subclass there exists a canonical monitor which also accepts the language itself. We also address the problem to decide monitorability in comparison with deciding liveness. The state of the art is as follows. Given a Büchi automaton, it is PSPACE-complete to decide liveness or monitorability. Given an LTL formula, deciding liveness becomes EXPSPACE-complete, but the complexity to decide monitorability remains open.

Introduction

Automata theoretic verification has its mathematical foundation in classical papers written in the 1950's and 1960's by Büchi, Rabin and others. Over the past few decades it became a success story with large scale industrial applications. However, frequently properties need to be checked against an unknown or very complex system. In such a situation classical exploration techniques like modelchecking might fail. The model-checking problem asks whether all runs satisfy a given specification. If the specification is written in monadic second-order logic, then all runs obeying the specification can be expressed e↵ectively by some Büchi automaton (BA for short). If the abstract model of the system is given by some finite transition system, then the model-checking problem becomes an inclusion problem on !-regular languages: all runs of the transition system must be accepted by the BA for the specification, too. In formal terms we wish to check L(A) ✓ L(') where A is the transition system of the system and ' is a formula for the specification. Typically testing inclusion is expensive, hence it might be better to check the equivalent assertion L(A) \ L(¬') = ;. This is a key fact, because then the verification problem becomes a reachability problem in finite graphs.

Whereas the formulas are typically rather small, so we might be able to construct the Büchi automaton for L(¬'), the transition systems tend to be very large. Thus, "state explosion" on the system side might force us to use weaker concepts. The idea is to construct a "monitor" for a given specification. A monitor observes the system during runtime. It is a finite deterministic automaton with at most two distinguished states ? and >. If it reaches the state ?, the monitor stops and raises an "alarm" that no continuation of the so far observed run will satisfy the specification. If it reaches >, the monitor stops because all continuations will satisfy the specification. Usually, this means we must switch to a finer monitor. Finally, we say that a language is monitorable, if in every state of the monitor it is possible to reach either ? or > or both.

The formal definition of monitorable properties has been given in [START_REF] Pnueli | PSL model checking and run-time verification via testers[END_REF] by Pnueli and Zaks. It generalizes the notion of a safety property because for a safety property some deterministic finite automaton can raise an alarm ? by observing a finite "bad prefix", once the property is violated. The extension to the more general notion of monitorability is that a monitorable property gives also a positive feedback >, if all extensions of a finite prefix obey the specification. Monitors are sometimes easy to implement and have a wide range of applications. See for example [START_REF] Leucker | A brief account of runtime verification[END_REF] and the references therein. Extensions of monitors have been proposed in more complex settings such as for stochastic automata [START_REF] Gondi | Monitoring the full range of !-regular properties of stochastic systems[END_REF][START_REF] Sistla | Monitorability of stochastic dynamical systems[END_REF] and for properties expressed in metric first-order temporal logic [START_REF] Basin | Monitoring metric first-order temporal properties[END_REF]. For practical use of monitors, various parameters may be relevant, in particular the size of the monitor or the runtime overhead generated by the monitor (see also the discussion in [START_REF] Tabakov | Optimized temporal monitors for SystemC[END_REF]).

In the present paper we discuss various monitor constructions. A monitor for a safety property L can have much less states than the smallest DBA accepting L. For example, let ⌃ = {a, b} and n 2 N. Consider the language L = a n ba⌃ ! \ ⌃ ⇤ bb⌃ ! . The reader is invited to check that L is a safety property and every DBA accepting L has more than n states. But there is a monitor with three states, only. The monitor patiently waits to see an occurrence of a factor bb and then switches to ?. Hence, there is no bound between a minimal size of an accepting DBA and the minimal size of a possible monitor. This option, that a monitor might be much smaller than any accepting DBA, has had one of the main motivations for the use of monitors.

There are many deterministic languages which are far away from being monitorable. Consider again ⌃ = {a, b} and let L be the deterministic language of "infinitely many a's". It is shown in [START_REF] Diekert | Topology, monitorable properties and runtime verification[END_REF] that L cannot be written as any countable union of monitorable languages. On the other hand, if L is monitorable and also accepted by some DBA with n states and a single initial state, then there is some monitor accepting L with at most n states.

In the last section of this paper we discuss the question how to decide whether a language is monitorable and its complexity. If the input is a Büchi automaton, then deciding safety, liveness, or monitorability is PSPACE-complete. If the input is an LTL formula, then deciding safety remains PSPACE-complete. It becomes surprisingly di cult for liveness: EXPSPACE-complete. For monitorability the complexity is wide open: we only know that it is PSPACE-hard and that monitorability can be solved in EXPSPACE.

Preliminaries

We assume that the reader is familiar with the basic facts about automata theory for infinite words as it is exposed in the survey [START_REF] Thomas | Automata on infinite objects[END_REF]. In our paper ⌃ denotes a finite nonempty alphabet. We let ⌃ ⇤ (resp. ⌃ ! ) be the set of finite (resp. infinite) words over ⌃. Usually, lower case letters like a, b, c denote letters in ⌃, u, . . . , z denote finite words, 1 is the empty word, and ↵, , denote infinite words. By language we mean a subset L ✓ ⌃ ! . The complement of L w.r.t. ⌃ ! is denoted by L c0 . Thus, L c0 = ⌃ ! \ L.

A Büchi automaton (BA for short) is a tuple A = (Q, ⌃, , I, F ) where Q is the nonempty finite set of states, I ✓ Q is the set of initial states, F ✓ Q is the set of final states, and ✓ Q ⇥ ⌃ ⇥ Q is the transition relation. The accepted language L(A) is the set of infinite words ↵ 2 ⌃ ! which label an infinite path in A which begins at some state in I and visits some state in F infinitely often. Languages of type L(A) are called !-regular.

If for each p 2 Q and a 2 ⌃ there is at most one q 2 Q with (p, a, q) 2 , then A is called deterministic. We write DBA for deterministic Büchi automaton. In a DBA we view as a partially defined function and we also write p • a = q instead of (p, a, q) 2 . Frequently it is asked that a DBA has a unique initial state. This is not essential, but in order to follow the standard notation (Q, ⌃, , q 0 , F ) refers to a BA where I is the singleton {q 0 }.

A deterministic weak Büchi automaton (DWA for short) is a DBA where all states in a strongly connected component are either final or not final. Note that a strongly connected component may have a single state because the underlying directed graph may have self-loops. A language is accepted by some DWA if and only if it is deterministic and simultaneously codeterministic. The result is in [START_REF] Staiger | Finite-state !-languages[END_REF] which in turn is based on previous papers by Staiger and Wagner [START_REF] Staiger | Automatentheoretische und automatenfreie Charakterisierungen topologischer Klassen regulärer Folgenmengen[END_REF] and Wagner [START_REF] Wagner | On omega-regular sets[END_REF].

According to [START_REF] Pnueli | PSL model checking and run-time verification via testers[END_REF] a monitor is a finite deterministic transition system M with at most two distinguished states ? and > such that for all states p either there exist a path from p to ?, or to >, or to both. It is a monitor for an !-language L ✓ ⌃ ! if the following additional properties are satisfied:

-If u denotes the label of a path from an initial state to ?, then u⌃ ! \ L = ;.

-If u denotes the label of a path from an initial state to >, then u⌃ ! ✓ L. A language L ✓ ⌃ ! is called monitorable if there exists a monitor for L. Thus, even non regular languages might be monitorable. If a property is monitorable, then the following holds:

8x 9w : xw⌃ ! ✓ L _ xw⌃ ! \ L = ; . (1)
The condition in (1) is not su cient for non-regular languages: indeed consider

L = {a n b n a | n 2 N}⌃ ! .
There is no finite state monitor for this language. In the present paper, the focus is on monitorable !-regular languages. For !regular languages (1) is also su cient; and Remark 2 below shows an equivalent condition for monitorability (although stronger for non-regular languages).

The common theme in "automata on infinite words" is that finite state devices serve to classify !-regular properties. The most prominent classes are:

-Deterministic properties: there exists a DBA.

-Deterministic properties which are simultaneously codeterministic: there exists a DWA.

-Safety properties: there exists a DBA where all states are final.

-Cosafety properties: the complement is a safety property.

-Liveness properties: there exists a BA where from all states there is a path to some final state lying in a strongly connected component.

-Monitorable properties: there exists a monitor. According to our definition of a monitor, not both states ? and > need to be defined. Sometimes it is enough to see ? or >. For example, let ; 6 = L 6 = ⌃ ! be a safety property and A = (Q, ⌃, , I, Q) be a DBA accepting L where all states are final. Since ; 6 = L we have I 6 = ;. Since L 6 = ⌃ ! , the partially defined transition function is not defined everywhere. Adding a state ? as explained above turns A into a monitor M for L where the state space is Q [ {?}. There is no need for any state >. The monitor M also accepts L. This is however not the general case.

Topological properties

A topological space is a pair (X, O) where X is a set and O is collection of subsets of X which is closed under arbitrary unions and finite intersections. In particular, ;,

X 2 O. A subset L 2 O is called open; and its complement X \ L is called closed.
For L ✓ X we denote by L the intersection over all closed subsets K such that L ✓ K ✓ X. It is the closure of L. The complement X \ L is denoted by

L c0 .
A subset L ✓ X is called nowhere dense if its closure L does not contain any open subset. The classical example of the uncountable Cantor set C inside the closed interval [0, 1] is nowhere dense. It is closed and does not have any open subset. On the other hand, the subset of rationals Q inside R (with the usual topology) satisfies Q = R. Hence, Q is "dense everywhere" although Q itself does not have any open subset.

The boundary of L is sometimes denoted as (L); it is defined by

(L) = L \ L c0 .
In a metric space B(x, 1/n) denotes the ball of radius 1/n. It is the set of y where the distance between x and y is less than 1/n. A set is open if and only if it is some union of balls, and the closure of L can be written as

L = \ n 1 [ x2L B(x, 1/n).
In particular, every closed set is a countable intersection of open sets. Following the traditional notation we let F be the family of closed subsets and G be the family of open subsets. Then F denotes the family of countable unions of closed subsets and G denotes the family of countable intersections of open subsets. We have just seen F ✓ G , and we obtain G ✓ F by duality. Since G is closed under finite union, G \ F is Boolean algebra which contains all open and all closed sets.

In this paper we deal mainly with !-regular sets. These are subsets of ⌃ ! ; and ⌃ ! is endowed with a natural topology where the open sets are defined by the sets of the form W ⌃ ! where W ✓ ⌃ ⇤ . It is called the Cantor topology. The Cantor topology corresponds to a complete ultra metric space: for example, we let d(↵, ) = 1/n for ↵, 2 ⌃ ! where n 1 2 N is the length of a maximal common prefix of ↵ and . (The convention is 0 = 1/1.)

The following dictionary translates notation about !-regular sets into its topological counterpart.

- [START_REF] Landweber | Decision problems for !-automata[END_REF].

Safety = closed sets = F . -Cosafety = open sets = G. -Liveness = dense = closure is ⌃ ! . -Deterministic = G , see
-Codeterministic = F , by definition and the previous line.

-Deterministic and simultaneously codeterministic = G \ F , by definition.

-Monitorable = the boundary is nowhere dense, see [START_REF] Diekert | Topology, monitorable properties and runtime verification[END_REF].

Monitorability depends on the ambient space X. Imagine we embed R into the plane R 2 in a standard way. Then R is a line which is nowhere dense in R 2 . As a consequence every subset L ✓ R is monitorable in R 2 . The same phenomenon happens for !-regular languages. Consider the embedding of {a, b} ! into {a, b, c} ! by choosing a third letter c. Then {a, b} ! is nowhere dense in {a, b, c} ! and hence, every subset L ✓ {a, b} ! is monitorable in {a, b, c} ! . The monitor has 3 states. One state is initial and by reading c we switch into the state ?. The state > can never be reached. In some sense this 3-state minimalistic monitor is useless: it tells us almost nothing about the language. Therefore the smallest possible monitor is rarely the best one.

Remark 1. In our setting many languages are monitorable because there exists a "forbidden factor", for example a letter c in the alphabet which is never used. More precisely, let L ✓ ⌃ ! be any subset and assume that there exists a finite word

f 2 ⌃ ⇤ such that either ⌃ ⇤ f⌃ ! ✓ L or ⌃ ⇤ f⌃ ! \ L = ;
. Then L is monitorable. Indeed, the monitor just tries to recognize ⌃ ⇤ f⌃ ! . Its size is |f | + 2 and can be constructed in linear time from f by algorithms of Matiyasevich [START_REF] Yu | Real-time recognition of the inclusion relation[END_REF] or Knuth-Morris-Pratt [START_REF] Knuth | Fast pattern matching in strings[END_REF].

Constructions of monitors

Remark 1 emphasizes that one should not try simply to minimize monitors. The challenge is to construct "useful" monitors. In the extreme, think that we encode a language L in printable ASCII code, hence it is a subset of {0, 1} ⇤ . But even in using a 7-bit encoding there were 33 non-printable characters. A monitor can choose any of them and then waits patiently whether this very special encoding error ever happens. This might be a small monitor, but it is of little interest. It does not even check all basic syntax errors.

Monitors for !-regular languages in G \ F

The !-regular languages in G \F are those which are deterministic and simultaneously codeterministic. In every complete metric space (as for example the Cantor space ⌃ ! ) all sets in G \ F have a boundary which is nowhere dense. Thus, deterministic and simultaneously codeterministic languages are monitorable by a purely topological observation, see [START_REF] Diekert | Topology, monitorable properties and runtime verification[END_REF].

Recall that there is another characterization of !-regular languages in G \F due to Staiger, [START_REF] Staiger | Finite-state !-languages[END_REF]. It says that these are the languages which are accepted by some DWA, thus by some DBA where in every strongly connected component either all states are final or none is final.

In every finite directed graph there is at least one strongly connected component which cannot be left anymore. In the minimal DWA (which exists and which is unique and where, without restriction, the transition function is totally defined) these end-components consist of a single state which can be identified either with ? or with >. Thus, the DWA is itself a monitor. Here we face the problem that this DWA might be very large and also too complicated for useful monitoring.

General constructions

Let w 2 ⌃ ⇤ be any word. Then the language L = w⌃ ! is clopen meaning simultaneously open and closed. The minimal monitor for w⌃ ! must read the whole word w before it can make a decision; and the minimal monitor has exactly |w| + 2 states. On the other hand, its boundary, L \ L c0 is empty and therefore nowhere dense. This suggests that deciding monitorability might be much simpler than constructing a monitor. For deciding we just need any DBA accepting the safety property L \ L c0 . Then we can see on that particular DBA whether L is monitorable, although this particular DBA might be of no help for monitoring. Phrased di↵erently, there is no bound between the size of a DBA certifying that L is monitorable and the size of an actual monitor for L.

Indeed, the standard construction for a monitor M L is quite di↵erent from a direct construction of the DBA for the boundary, see for example [START_REF] Diekert | Topology, monitorable properties and runtime verification[END_REF]. The construction for the monitor M L is as follows. Let L ✓ ⌃ ! be monitorable and given by some BA. First, we construct two DBAs: one DBA with state set Q 1 , for the closure L and another one with state set Q 2 for the closure of the complement L c0 . We may assume that in both DBAs all states are final and reachable from a unique initial state q 01 and q 02 , respectively. Second, let

Q 0 = Q 1 ⇥ Q 2 . Now, if
we are in a state (p, q) 2 Q 0 and we want to read a letter a 2 ⌃, then exactly one out of the three possibilities can happen.

1. The states p•a and q •a are defined, in which case we let (p, q)•a = (p•a, q •a).

2. The state p • a is not defined, in which case we let (p, q) • a = ?.

3. The state q • a is not defined, in which case we let (p, q) • a = >.

Here ? and > are new states. Moreover, we let q•a = q for q 2 {?, >} and a 2 ⌃. Hence, the transition function is totally defined. Finally, we let Q ✓ Q 0 [ {?, >} be the subset which is reachable from the initial state (q 01 , q 02 ). Since L is monitorable, Q \ {?, >} 6 = ;; and Q defines a set of a monitor M L . Henceforth, the monitor M L above is called a standard monitor for L. The monitor has exactly one initial state. From now on, for simplicity, we assume that every monitor M has exactly one initial state and that the transition function is totally defined. Thus, we can denote a monitor M as a tuple M = (Q, ⌃, , q 0 , ?, >).

(

Here, :

Q ⇥ ⌃ ! Q, (p, a) 7 ! p
• a is the transition function, q 0 is the unique initial state, ? and > are distinguished states with Q \ {?, >} 6 = ;. L and arcs (L(x), a, L(xa)) where x 2 ⌃ ⇤ and a 2 ⌃. There is a canonical initial state L = L(1), but unlike in the case of regular sets over finite words there is no good notion of final states in Q L for infinite words. The right congruence is far too coarse to recognize L, in general. For example, consider the deterministic language L of "infinitely many a's" in {a, b} ! . For all x we have L = L(x), but in order to recognize L we need two states.

Definition 1. Let M = (Q, ⌃, , q 0 , ?, >), M 0 = (Q 0 , ⌃, 0 , q 0 0 , ?, >) be moni- tors. A morphism between M and M 0 is mapping ' : Q [ {?, >} ! Q 0 [ {?, >} such that '(q 0 ) = q 0 0 , '(?) = ?, '(>) = >,
It is classical that if L is !-regular, then the set Q L is finite, but the converse fails badly [22, Section 2]: there are uncountably many languages where |Q L | = 1. To see this define for each ↵ 2 ⌃ ! a set

L ↵ = { 2 ⌃ ! | ↵
| = 1 since L ↵ (x) = L ↵ for all x.
Recall that a monitor is a DBA where the monitoring property is not defined using final states, but it is defined using the states ? and >. Thus, a DBA with an empty set of final states can be used as a monitor as long as ? and > have been assigned and the required properties for a monitor are satisfied.

Proposition 1. Let L ✓ ⌃ !
be !-regular and monitorable. Assume that L is accepted by some BA with n states. As above let

Q L = {L(x) | x 2 ⌃ ⇤ } and denote ? = ; and > = ⌃ ! . Then |Q L |  2 n and Q L [ {>, ?
} is the set of states for a monitor for L. At least one of the states in {>, ?} is reachable from the initial state L = L(1). The monitor in Proposition 1 with state space Q L is denoted by A L henceforth. We say that A L is the right-congruential monitor for L.

Proposition 2. Let A be the right-congruential monitor for L. Then the mapping

L(x) 7 ! '(L(x)) = (L (x), L c0 (x))
induces a canonical epimorphism from A L onto some standard monitor M L .

Proof. Observe that L (x) = L(x) and L c0 (x) = L(x) c0 . Hence, (L (x), L c0 (x)) = (L(x) , L(x) c0 ) and '(L(x)) is well-defined. Now, if L (x) 6 = ; and L c0 (x) 6 = ;, then '(L(x)) 2 Q where Q is the state space of the standard monitor M. If L (x) = ; then we can think that all (;, L c0 (x)) denote the state ?; and if L c0 (x) = ; then we can think that all (L (x), ;) denote the state >. u t

Corollary 1. Let L ✓ ⌃ ! be monitorable and given by some BA with n states. Then some standard monitor M L for L has at most 2 n states.

Proof. Without restriction we may assume that in the BA (Q, ⌃, , I, F ) accepting L every state q 2 Q leads to some final state. The usual subset construction leads first to a DBA accepting L , where all states are final and the states of this DBA are the nonempty subsets of Q. Thus, these are 2 n 1 states. Adding the empty set ; = ? we obtain a DBA with 2 n states where the transition function is defined everywhere. If the complement L c0 is dense, this yields a standard monitor. In the other case we can use the subset construction also for a DBA accepting L c0 . In this case we remove all subsets P ✓ Q where

L(Q, ⌃, , P, F ) = ⌃ ! . (Note, for all a 2 ⌃ we have: if L(Q, ⌃, , P, F ) = ⌃ ! and P 0 = {q 2 Q | 9p 2 P : (p, a, q) 2 }, then L(Q, ⌃, , P 0 , F ) = ⌃ ! , too.
) Thus, if L c0 is not dense, then the construction for a standard monitor has at most 2 n 2 states of the form (P, P ) where ; 6 = P and L(Q, ⌃, , P, F ) 6 = ⌃ ! . In addition there exists the reachable state > and possibly the state ?. u t Proposition 2 leads to the question of a canonical minimal monitor, at least for a safety language where a minimal accepting DBA exists. The answer is "no" as we will see in Example 1 later.

Let us finish the section with a result on arbitrary monitorable subsets of ⌃ ! which is closely related to [21, Lemma 2]. Consider any subset L ✓ ⌃ ! where the set of quotients Q L = {L(x) | x 2 ⌃ ⇤ } is finite (="zustandsendlich" or "finite state"in the terminology of [START_REF] Staiger | Reguläre Nullmengen[END_REF]). If Q L is finite, then L is monitorable if and only if the boundary is nowhere dense. In every topological space this latter condition is equivalent to the condition that the interior of L is dense in its closure L . Translating Staiger's result in [START_REF] Staiger | Reguläre Nullmengen[END_REF] to the notion of monitorability we obtain the following fact. Proposition 3. Let L ✓ ⌃ ! be any monitorable language and let M be a monitor for L with n states. Then there exists a finite word w of length at most (n 1) 2 such that for all x 2 ⌃ ⇤ we have either xw⌃ ! ✓ L or xw⌃ ! \ L = ;.

Proof. We may assume that n 1 and that the state space of M is included in {1, . . . , n 1, ?, >}. Merging > and ? into a single state 0 we claim that there is a word w of length at most (n 1) 2 such that q • w = 0 for all 0  q  n 1. Since L is monitorable, there is for each q 2 {0, . . . , n 1} a finite word v q of length at most n 1 such that q • v q = 0. By induction on k we may assume that there is a word w k of length at most k(n 1) such that for each q 2 {0, . . . , k} we have q • w k = 0. (Note that the assertion trivially holds for k = 0.) If k n 1 we are done: w = w n 1 . Otherwise consider the state q = k + 1 and the state p = q • w k . Define the word w k+1 by w k+1 = w k v p . Then the length of w k+1 is at most (k + 1)(n 1). Since w k is a prefix of w k+1 and since 0 • v = v for all v, we have q • w k+1 = 0 for all 0  q  k + 1. The length bound (n 1) 2 is not surprising. It confirms Černý's Conjecture in the case of monitors. (See [START_REF] Volkov | Synchronizing automata and the Černý conjecture[END_REF] for a survey on Černý's Conjecture.) Actually, in the case of monitors with more than 3 states the estimation of the length of the "reset word" is not optimal. For example in the proof of Proposition 3 we can choose the word v 1 to be a letter, because there must be a state with distance at most one to 0. The precise bound is n+1 2 = (n + 1)n/2 if the alphabet is allowed to grow with n [19, Theorem 6.1]. If the alphabet is fixed, then the lower bound for the length of w is still in n 2 /4 + ⌦(n) [START_REF] Martugin | A series of slowly synchronizing automata with a zero state over a small alphabet[END_REF].

Monitorable deterministic languages

The class of monitorable languages form a Boolean algebra and every !-regular set L can be written as a finite union L = S n i=1 L i \ K i where the L i and K i are deterministic !-regular, [START_REF] Thomas | Automata on infinite objects[END_REF]. Thus, if L is not monitorable, then one of the deterministic L i or K i is not monitorable. This motivates to study monitorable deterministic languages more closely. Definition 2. Let L ✓ ⌃ ! be deterministic !-regular. A deterministic Büchi monitor ( DBM for short) for L is a tuple B = (Q, ⌃, , q 0 , F, ?, >)

where A = (Q, ⌃, , q 0 , F ) is a DBA with L = L(A) and where (Q, ⌃, , q 0 , ?, >) is a monitor in the sense of Equation ( 2) for L. The next proposition justifies the definition. Proposition 4. Let L ✓ ⌃ ! be any subset. Then L is a monitorable deterministic !-regular language if and only if there exists a DBM for L.

Proof. The direction from right to left is trivial. Thus, let L be monitorable and let L = L(A) for some DBA A = (Q, ⌃, , q 0 , F ) where all states are reachable from the initial state q 0 . For a state p 2

Q let L(p) = L(Q, ⌃, , p, F ). If L(p) = ;, then L(p • a) = ;; and if L(p) = ⌃ ! , then L(p • a) = ⌃ ! .
Thus, we can merge all states p with L(p) = ; into a single non-final state ?; and we can merge all all states p with L(p) = ⌃ ! into a single final state > without changing the accepted language. All states are of the form q 0 • x for some x 2 ⌃ ⇤ ; and, since L is monitorable, for each x either there is some y with xy⌃ ! \ L = ; or there is some y with xy⌃ ! ✓ L (or both). In the former case we have q 0 • xy = ? and in the latter case we have q 0 • xy = >. u t Corollary 2. Let L ✓ ⌃ ! be a monitorable deterministic !-regular language and A be a DBA with n states accepting L. Let B be a DBM for L with state set Q B where the size of Q B is as small as possible. Let further Q R (resp. Q M ) be the state set of the congruential (resp. smallest standard) monitor for L. Then we have

n |Q B | |Q R | |Q M | . Example 1. Let ⌃ = {a, b} and = {a, b, c, d}. 1. For n 2 N consider L = a n b⌃ ! \ ⌃ ⇤ bb⌃ ! .
It is a safety property. Hence, we have L = L. Moreover, ⌃ ⇤ bb⌃ ! is a liveness property (i.e., dense). Hence L c0 = ⌃ ! . It follows that the standard monitor is just the minimal DBA for L augmented by the state ?. There are exactly n + 4 right-congruence classes defined by prefixes of the words a n ba and a n b 2 . We have L(a n b 2 ) = ;. Hence reading a n b 2 leads to the state ?. This, shows that the inequalities in Corollary 2 become equalities in that example. On the other hand b 2 is a forbidden factor for L. Hence there is a 3 state monitor for L. Still there is no epimorphism from the standard monitor onto that monitor, since in the standard monitor we have L(a n+1 ) = ; but in the 3-state monitor ? has not an incoming arc labeled by a.

2. Every monitor for the language ⌃ ⇤ (bab [ b 3 )⌃ ! has at least 4 states. There are three monitors with 4 states which are pairwise non-isomorphic.

3. Let L = (b ⇤ a) ! [ {a, b} ⇤ c{a, b, c} ! ✓ ! .
Then L is monitorable and deterministic, but not codeterministic. Its minimal DBM has 4 states, but the congruential monitor Q R has 3 states, only. We have L = {a, b, c} ! and L c0 = ! . Hence, the smallest standard monitor has two states. In particular, we have 5 Deciding liveness and monitorability

|Q B | > |Q R | > |Q M |, see also Figure 1.

Decidability for Büchi automata

It is well-known that decidability of liveness (monitorability resp.) is PSPACEcomplete for Büchi automata. The following result for liveness is classic, for monitorability it was shown in [START_REF] Diekert | On distributed monitoring of asynchronous systems[END_REF].

Proposition 5. The following two problems are PSPACE-complete:

-Input: A Büchi automaton A = (Q, ⌃, , I, F ).
-Question 1: Is the accepted language L(A) ✓ ⌃ ! live? -Question 2: Is the accepted language L(A) ✓ ⌃ ! monitorable?

Proof. Both problems can be checked in PSPACE using standard techniques. We sketch this part for monitorability. The procedure considers, one after another, all subsets P such that P is reachable from I by reading some input word. For each such P the procedure guesses some P 0 which is reachable from P . It checks that either L(A 0 ) = ; or L(A 0 ) = ⌃ ! , where A 0 = (Q, ⌃, , P 0 , F ). If both tests fail then the procedure enters a rejecting loop.

If, on the other hand, the procedure terminates after having visited all P , then L(A) is monitorable.

For convenience of the reader we show PSPACE-hardness of both problems by adapting the proof in [START_REF] Diekert | On distributed monitoring of asynchronous systems[END_REF].

We reduce the universality problem for non-deterministic finite automata (NFA) to both problems. The universality problem for NFA is well-known to be PSPACE-complete.

Start with an NFA A = (Q 0 , , 0 , q 0 , F 0 ) where 6 = ;. We use a new letter b / 2 and we let ⌃ = [ {b}.

We will construct Büchi automata B 1 and B 2 as follows. We use three new states d, e, f and we let Q = Q 0 [ {d, e, f }, see Figure ??. The initial state is the same as before: q 0 . Next, we define . We keep all arcs from 0 and we add the following new arcs.

-

q b ! d a ! e a ! e for all q 2 Q 0 \ F 0 and all a 2 . -e b ! d b ! d -q b ! f c ! f for all q 2 F 0 and all c 2 ⌃.
Let us define two final sets of states: F 1 = {f } and F 2 = {d, f }. Thus, we have constructed Büchi automata B 1 and B 2 where

B i = (Q, , , q 0 , F i ) for i = 1, 2.
For the proof of the proposition it is enough to verify the following two claims which are actually more precise than needed.

1. The language L(B 1 ) is monitorable. It is live if and only if If L(A) = ⇤ , then we have L(B 1 ) = L(B 2 ) = ⌃ ! , so both languages are live and monitorable.

L(A) = ⇤ . 2. The language L(B 2 ) is live. It is monitorable if and only if L(A) = ⇤ . Q 0 \ F 0
If L(A) 6 = ⇤ , then there exists some word u / 2 L(A) and hence reading ub we are necessarily in state d. It follows that ub⌃ ! \ L(B 1 ) = ; and L(B 1 ) is not live. Still, L(B 1 ) is monitorable. Now, for all w 2 ⌃ ⇤ we have wb ! 2 L(B 2 ). Hence, L(B 2 ) is live. However, if u / 2 L(A), then after reading ub we are in state

d. Now, choose some letter a 2 . For all v 2 ⌃ ⇤ we have ubva ! / 2 L(B 2 ), but ubvb ! 2 L(B 2 ). Hence, if L(A) 6 = ⇤ , then L(B 2 ) is not monitorable. u t

Decidability for LTL

We use the standard syntax and semantics of the linear temporal logic LTL for infinite words over some finite nonempty alphabet ⌃. We restrict ourselves the pure future fragment and the syntax of LTL ⌃ [XU] is given as follows.

'

::= > | a | ¬' | ' _ ' | ' XU '
, where a ranges over ⌃. The binary operator XU is called the next-until modality.

In order to give the semantics we identify each ' 2 LTL ⌃ with some firstorder formula '(x) in at most one free variable. The identification is done as usual by structural induction. The formula a becomes a(x) = P a (x), where P a (x) is the unary predicate saying that the label of position x is the letter a. The formula "' neXt-Until " is defined by:

(' XU )(x) = 9z : (x < z ^ (z) ^8y : '(y) _ y  x _ z  y).
Finally let ↵ 2 ⌃ ! be an infinite word with the first position 0, then we define ↵ |= ' by ↵ |= '(0); and we define

L(') = {↵ 2 ⌃ ! | ↵ |= '}.
Languages of type L(') are called LTL definable, It is clear that every LTL definable language is first-order definable; and Kamp's famous theorem [START_REF] Kamp | Tense Logic and the Theory of Linear Order[END_REF] states the converse. In particular, given L(') there exists a BA A such that L(') =

L(A).

There are examples where the size of the formula ' is exponentially smaller than the size of any corresponding BA A.

For a survey on first-order definable languages we refer to [START_REF] Diekert | First-order definable languages[END_REF]. By LTL decidability of a property P we mean that the input is a formula ' 2 LTL ⌃ and we ask whether property P holds for L('). By Proposition 5 we obtain straightforwardly the following lower and upper bounds for the LTL decidability of monitorability and liveness.

Remark 3. The following two problems are PSPACE-hard and can be solved in EXPSPACE:

-Input: A formula ' 2 LTL ⌃ .
-Question 1: Is the accepted language L(') ✓ ⌃ ! live? -Question 2: Is the accepted language L(') ✓ ⌃ ! monitorable? Remark 3 is far from satisfactory since there is huge gap between PSPACEhardness and containment in EXPSPACE. Very unfortunately, we were not able to make the gap any smaller for monitorability. There was some belief in the literature that, at least, LTL liveness can be tested in PSPACE, see for example [START_REF] Nitsche | Relative liveness and behavior abstraction (Extended abstract)[END_REF]. But surprisingly this last assertion is wrong: testing LTL liveness is EXPSPACE-complete! Proposition 6. Deciding LTL liveness is EXPSPACE-complete:

-Input: A formula ' 2 LTL ⌃ .
-Question Is the accepted language L(') ✓ ⌃ ! live? EXPSPACE-completeness of liveness was proved by Muscholl and Walukiewicz in 2012, but never published. Independently, it was proved by Orna Kupferman and Gal Vardi in [START_REF] Kupferman | On relative and probabilistic finite counterabilty[END_REF].

We give a proof of Proposition 6 in Sections 5.3 and 5.4 below. We also point out why the proof technique fails to say anything about the hardness to decide monitorability. Our proof for Proposition 6 is generic. This means that we start with a Turing machine M which accepts a language L(M ) ✓ ⇤ in EXPSPACE. We show that we can construct in polynomial time a formula '(w) 2 LTL ⌃ such that w 2 L(M ) () L('(w)) ✓ ⌃ ! is not live.

Encoding EXPSPACE computations

For the definition of Turing machines we use standard conventions, very closely to the notation e.g. in [START_REF] Hopcroft | Introduction to Automata Theory, Languages and Computation[END_REF]. Let L = L(M ) be accepted by a deterministic Turing machine M , where M has set of states Q and the tape alphabet is containing a "blank" symbol B. We assume that for some fixed polynomial p(n) n +2 the machine M uses on an input word w 2 ( \ {B}) ⇤ of length n strictly less space than 2 N 2, where N = p(n). (It does not really matter that M is deterministic.) Configurations are words from ⇤ (Q ⇥ ) ⇤ of length precisely 2 N , where the head position corresponds to the symbol from Q ⇥ . For technical reasons we will assume that the first and the last symbol in each configuration is B. Let

A = [ (Q ⇥ ).
If the input is nonempty word w = a 1 • • • a n where the a i are letters, then the initial configuration is defined here as

C 0 = B(q 0 , a 1 )a 2 • • • a n BBBBB • • • B | {z } 2 N n 1 times
.

For t 0 let C t be configuration of M at time t during the computation starting with the initial configuration C 0 on input w. We may assume that the computation is successful if and only if there is some t such that a special symbol, say q f , appears in C t . Thus, we can write each C t as a word

C t = a 0,t • • • a m,t
with m = 2 N 1; and we have w 2 L(M ) if and only if there are some i 1 and t 1 such that a i,t = q f . In order to check that a sequence C 0 , C 1 , . . . is a valid computation we may assume that the Turing machine comes with a table

✓ A 4 such that the following formula holds:

8t > 0 81  i < 2 N 1 : (a i 1,t 1 , a i,t 1 , a i+1,t 1 , a i,t ) 2 .
Without restriction we have (B, B, B, B) 2 , because otherwise M would accept only finitely many words.

We may express that we can reach a final configuration C t by saying: 9t 1 91  i < 2 N : a i,t = q f . As in many EXPSPACE-hardness proofs, for comparing successive configurations we need to switch to a slightly di↵erent encoding, by adding the tape position after each symbol from A. To do so, we enlarge the alphabet A by new symbols 0, 1, $, #, k 1 , . . . k N which are not used in any C t so far. Hence, ⌃ = A [ {0, 1, $, #, k 1 , . . . k N }. We encode a position 0  i < 2 N by using its binary representation with exactly N bits. Thus, each i is written as a word bin

(i) = b 1 • • • b N where each b p 2 {0, 1}. In particular, bin(0) = 0 N , bin(1) = 0 N 1 1, . . . , bin(2 N 1) = 1 N . Henceforth, a configuration C t = a 0,t • • • a m,t with m = 2 N 1 is encoded as a word c t = a 0,t bin(0) • • • a m,t bin(m)$.
Words of this form are called stamps in the following. Each stamp has length 2 N • N + 1. If a factor bin(i) occurs, then either i = m (i.e., bin(i) = 1 N ) and the next letter is $ or i < m and the next letter is some letter from the original alphabet A followed by the word bin(i + 1). Now we are ready to define a language L = L(w) which has the property that L is not live if and only if w 2 L(M ). We describe the words ↵ 2 ⌃ ! which belong to L as follows.

1. Assume that ↵ does not start with a prefix of the form c 0 • • • c `#, where c 0 corresponds to the initial configuration w.r.t. w, each c t is a stamp and in the stamp c `the symbol q f occurs. Then ↵ belongs to L.

2. Assume now that ↵ starts with a prefix c 0 • • • c `# as above. Then we let ↵ belong to L if and only if the set of letters occurring infinitely often in ↵ witness that the prefix c 0 • • • c `of stamps is not a valid computation. Thus, we must point to some t 1 and some position 1  i < m such that (a i 1,t 1 , a i,t 1 , a i+1,t 1 , a i,t ) / 2 . The position i is given as bin

(i) = b 1 • • • b N 2 {0, 1} N .
The string bin(i) defines a subset of ⌃:

I(i) = {k p 2 {k 1 , . . . , k N } | b p = 1}.
The condition for ↵ to be in L is that for some t the mistake from c t 1 to c t is reported by (a i 1,t 1 , a i,t 1 , a i+1,t 1 , a i,t ) / 2 and the position i such that I(i) equals the set of letters k p which appear infinitely often in ↵. Note that since we excluded mistakes at positition i = 0 (because of the leftmost B), the set I(i) is non-empty.

Lemma 1. The language L = L(w) is not live if and only if w 2 L(M ).

Proof. First, let w 2 L(M ). Then we claim that L is not live. To see this let

u = c 0 • • • c `#, where the prefix c 0 • • • c `is a valid accepting computation of M . There is no mistake in c 0 • • • c `.
Thus we have u⌃ ! \ L = ;, so indeed, L is not live.

Second, let w / 2 L(M ). We claim that L is live. Consider any u 2 ⌃ ⇤ . Assume first that u does not start with a prefix of the form c 0 • • • c `#, where c 0 corresponds to the initial configuration w.r.t. w, each c t is a stamp and in the stamp c

`the symbol q f occurs. Then we we have u⌃ ! ✓ L. Otherwise, assume that c 0 • • • c `# is a prefix of u and that all c t 's are stamps, with c 0 initial and c `containing q f . There must be some mistake in c 0

• • • c `#,
say for some i and t. Let I(i) be as defined a above. As i 1 we have I(i) 6 = ;. Therefore we let be any infinite word where the set of letters appearing infinitely often is exactly the set I(i). By definition of L we have u 2 L. Hence,

L is live. u t

There are other ways to encode EXPSPACE computations which may serve to prove Proposition 6, see for example [START_REF] Kupferman | On relative and probabilistic finite counterabilty[END_REF]. However, these proofs do not reveal any hardness for LTL monitorability. In particular, they do not reveal EX-PSPACE or EXPTIME hardness. For our encoding this is explained in Remark 4.

Remark 4. Since are interested in EXPSPACE-hardness, we may assume that there infinitely many w with w / 2 L(M ). Let n be large enough, say n 3 and w / 2 L(M ), then (B, (q 0 , a 1 ), a 2 , q f ) / 2 , where w = a 1 a 2 • • • because otherwise w 2 L(M ). Define c 1 just as the initial stamp c 0 with the only di↵erence that the letter (q 0 , a 1 ) is replaced by the symbol q f . Let u = c 0 c 1 #, then for every v 2 ⌃ ⇤ we have that uv(k N ) ! 2 L (i.e., there is a mistake at position 1), but uv(k 1 k 2 • • • k N ) ! \ L = ; (i.e., there is no mistake at position 2 N 1) because (B, B, B, B) 2 . Thus, L is not monitorable.

Proof of Proposition 6

LTL liveness is in EXPSPACE by Remark 3. The main ideas for the proof are in the previous subsection. We show that we can construct in polynomial time on input w some ' 2 LTL ⌃ such that L(') = L(w). This can be viewed as a standard exercise in LTL. The solution is a little bit tedious and leads to a formula of at most quadratic size in n. The final step in the proof is to apply Lemma 1.

u t

Conclusion and outlook

In the paper we studied monitorable languages from the perspective of what is a "good monitor". In some sense we showed that there is no final answer yet, but monitorability is a field where various interesting questions remain to be answered.

Given an LTL formula for a monitorable property one can construct monitors of at most doubly exponential size; and there is some indication that this is the best we can hope for, see [START_REF] Bauer | Monitoring of real-time properties[END_REF]. Still, we were not able to prove any hardness for LTL monitorability beyond PSPACE. This does not mean anything, but at least in theory, it could be that LTL monitorability cannot be tested in EXPTIME, but nevertheless it is not EXPTIME-hard.

There is also another possibility. Deciding monitorability might be easier than constructing a monitor. Remember that deciding monitorability means to test that the boundary is nowhere dense. However we have argued that a DBA for the boundary does not give necessarily any information about a possible monitor, see the discussion at the beginning of Section 3.2.

A more fundamental question is about the notion of monitorability. The definition is not robust in the sense that every language becomes monitorable simply by embedding the language into a larger alphabet. This is somewhat puzzling, so the question is whether a more robust and still useful notion of monitorability exist.

Finally, there is an interesting connection to learning. In spite of recent progress to learn general !-regular languages by [START_REF] Angluin | Learning regular omega languages[END_REF] it not known how to learn a DBA for deterministic !-regular languages in polynomial time. The best result is still due to Maler and Pnueli in [START_REF] Maler | On the learnability of infinitary regular sets[END_REF]. They show that it is possible to learn a DWA for a !-regular language L in G \ F in polynomial time. The queries to the oracle are membership question "uv ! 2 L?" where u and v are finite words and the query whether a proposed DWA is correct. If not, the oracle provides a shortest counterexample of the form uv ! .

Since a DWA serves also as a monitor we can learn a monitor the very same way, but beyond G \ F it is not known that membership queries to L and queries whether a proposed monitor is correct su ce. As a first step one might try find out how to learn a deterministic Büchi monitor in case it exists. This is a natural class beyond G \ F because canonical minimal DBA for these languages exist. Moreover, just as for DWA this minimal DBA is an DBM, too.

Another interesting branch of research is monitorability in a distributed setting. A step in this direction for infinite Mazurkiewicz traces was outlined in [START_REF] Diekert | On distributed monitoring of asynchronous systems[END_REF].

  and '(p • a) = '(p) • a for all p 2 Q and a 2 ⌃. If ' is surjective, then ' is called an epimorphism. Another canonical monitor construction uses the classical notion of rightcongruence. A right-congruence for the monoid ⌃ ⇤ is an equivalence relation ⇠ such that x ⇠ y implies xz ⇠ yz for all x, y, z 2 ⌃ ⇤ . There is a canonical rightcongruence ⇠ L associated with every !-language L ✓ ⌃ ! : for x 2 ⌃ ⇤ denote by L(x) = {↵ 2 ⌃ ! | x↵ 2 L} the quotient of L by x. Then defining ⇠ L by x ⇠ L y () L(x) = L(y) yields a right-congruence. More precisely, ⌃ ⇤ acts on the set of quotients Q L = {L(x) | x 2 ⌃ ⇤ } on the right, and the formula for the action becomes L(x) • z = L(xz). Note that this is well-defined. This yields the associated automaton [22, Section 2]. It the finite deterministic transition system with state set Q

u t Remark 2 .

 2 The interest in Proposition 3 is that monitorability can be characterized by a single alternation of quantifiers. Instead of saying that 8x 9w (8↵ : xw↵ 2 L) _ (8↵ : xw↵ / 2 L) it is enough to say 9w 8x (8↵ : xw↵ 2 L) _ (8↵ : xw↵ / 2 L).

Fig. 1 .

 1 Fig. 1. Monitors B, R, M for L = L(B).

Fig. 2 .

 2 Fig.2. PSPACE-hardness for liveness and monitorability for Büchi automata.

  and share an infinite su x}. All L ↵ are countable, but the union {L ↵ | ↵ 2 ⌃ ! } covers the uncountable Cantor space ⌃ ! . Hence, there are uncountably many L ↵ . However, |Q L↵

Acknowledgment

The work was done while the first author was visiting LaBRI in the framework of the IdEx Bordeaux Visiting Professors Programme in June 2015. The hospitality of LaBRI and their members is greatly acknowledged.

The authors thank Andreas Bauer who communicated to us (in June 2012) that the complexity of LTL-liveness should be regarded as open because published proofs stating PSPACE-completeness were not convincing. We also thank Ludwig Staiger, Gal Vardi, and Mikhail Volkov for helpful comments.


Calvo Yanguas

Elvira Donázar

Trillo Lado

A Formal Definition for Configuration

Keywords: Configuration, Permutation, Symmetric group, G-module, Relational database, Keyword-based search, Keyword-based queries

There exists a wide set of techniques to perform keyword-based search over relational databases but all of them match the keywords in the users' queries to elements of the databases to be queried as first step. The matching process is a time-consuming and complex task. So, improving the performance of this task is a key issue to improve the keyword based search on relational data sources.

In this work, we show how to model the matching process on keyword-based search on relational databases by means of the symmetric group. Besides, how this approach reduces the search space is explained in detail.

Introduction

In the last decade, the amount of large digital structured data available on the Web is increasing due to the success of initiatives such as DBpedia, Linked Open Data and Semantic Web [START_REF] Amaro | Collecting and generating new ideas[END_REF]. Moreover, keyword-based search has become the de-facto standard for searching information on the Web since its adoption by the main web search engines, such as Google, at the end of the 90's. The reasons of its success are mainly its simplicity and intuitiveness, as it does not require users searching information to know either any formal language, such as SQL [START_REF] Leon | SQL: A Complete Reference[END_REF] or SPARQL [START_REF] Prud | SPARQL query language for RDF[END_REF], or how the data and documents are stored.

This context has made to increase the interest in supporting keyword search over structured databases, and, in particular, over relational databases [START_REF] Yu | Keyword Search in Databases[END_REF]. There exists a wide set of techniques and methods to perform keywordbased search over relational databases, classified under two main groups: graph-based approaches and schema-based approaches [START_REF] Yu | Keyword search in relational databases: A survey[END_REF]. Nevertheless, all of them require matching the keywords in the users' queries to elements of the databases to be queried as first step, i.e., they require to explore what in Keymantic [START_REF] Bergamaschi | Keyword search over relational databases: A metadata approach[END_REF] is defined as to find configurations of the users' queries. Thus, exploring possible configurations by using specific algorithms, such as Hungarian algorithm, is required to optimize the search.

In this paper, we propose a formal definition for configurations to improve the performance of current techniques such as Keymantic. In particular, we define configurations as given types of elements of the symmetric group, S n , in order to establish equivalence relations among different configurations, and, therefore, in order to reduce the number of configurations to evaluate.

Moreover, since there is a natural one to one correspondence between the conjugacy classes of S n and the partitions of n and there exists an order in partitions of n, then, it is possible to order configurations.

Fundamental concepts

In the following, the bases to formalize the keyword based search over relational databases are described.

Keyword Search over Relational Databases

Definition 2.1 A database, D, [2] is a collection of relational tables , R(A 1 , A 2 , • • • , A n ), where R is the name of the table and A 1 , A 2 , • • •, A n its attributes.

Definition 2.2

The vocabulary of D, denoted by V D , is the set of all its relation names, their attributes and their respective domains. A database term is a member of this vocabulary V D .

A keyword query q is an ordered list of keywords {k 1 , k 2 , • • • , k N }. Each keyword is a specification about the element of interest. Definition 2.3 A configuration C of a keyword query q on a database D [START_REF] Bergamaschi | Keyword search over relational databases: A metadata approach[END_REF] is an injective map from the keywords in q to database terms in the vocabulary of D.

It is made the natural assumption that each keyword can be mapped to only one database term, not two keywords can be mapped into the same database term and there are no unjustified keywords.

We must map the N keywords in a query to the |V D | database terms in the vocabulary of D, so there are

|V D |! (|V D | -N )! possible configurations. V D = {X|∃R(A 1 , • • • , A n )∈D s.t. X=R ∨ X=A k ∨ X=Dom(A k ), 1≤k≤n}, so |V D | = 2 * |D| i=1 |R i | + |D|,
with |R i | denoting the arity of the relation R i and |D| the number of tables in the database.

To give a formal definition for a configuration we start by considering the keyword query and the vocabulary of the database as sets of numbers

{1, 2, • • • , N }, {1, 2, • • • , |V D |} respectively, where N ≤ |V D |.
The definition of a configuration can be interpreted as an injective correspondence

{1, 2, • • • , N } -→ {1, 2, • • • , |V D |},
that can be extended to a one to one correspondence

{1, 2, • • • , N, N + 1, • • • , |V D |} -→ {1, 2, • • • , |V D |},
that is, we define it as an element of the symmetric group S |V D | .

The Symmetric Group

Definition 2.4 The symmetric group, S n , [START_REF] Sagan | The Symmetric Group. Representations, Combinatorial Algorithms, and Symmetric Funtions[END_REF] is the set of all bijections

{1, 2, • • • , n} -→ {1, 2, • • • , n},
also called permutations, using composition as the multiplication. We multiply permutations from right to left, thus πσ is the bijection obtained by first applying σ, followed by π.

Definition 2.5 Given π ∈ S n and i ∈ {1, 2, • • • , n}, the elements i, π(i), π 2 (i), • • • cannot all be distinct. Taking the first power r that π r (i) = i, we have the r-cycle, or cycle of length r, i, π(i), π 2 (i), • • • , π r-1 (i) . A 1-cycle of π is called a fixedpoint.
Definition 2.6 Given π ∈ S n and m k the number of its k-cycles, the cycle type of π, or simply the type, is the expression of the form

(1 m 1 , 2 m 2 , • • • , n mn ) . Definition 2.7 A partition of n is a sequence λ = (λ 1 , λ 2 , • • • , λ l )
where the λ i are weakly decreasing and

|λ| def = l i=1 λ i = n.
We use the notation λ ⊢ n.

To obtain the partition of a permutation, for each m k = 0 in cycle type we put m k times the value of k, starting with the biggest k and decreasing. That is another way to give the cycle type.

We are interested in permutations in S |V D | that have only cycles of length ≤ N + 1 and with no more than a number bigger than N in each cycle, therefore permutations in

S |V D | with m N +2 = • • • = m |V D | = 0. Definition 2.8 Elements g, h ∈ S n are conjugates if g = khk -1
for some k ∈ S n . The conjugacy class of g ∈ S n is

K g = h ∈ G|∃k ∈ G s.t. khk -1 = g ,
the set of all elements conjugate to g.

Conjugacy is an equivalence relation in S n . Two permutations are in the same conjugacy class if and only if they have the same cycle type and, using K λ for K g when g has type λ (see [START_REF] Sagan | The Symmetric Group. Representations, Combinatorial Algorithms, and Symmetric Funtions[END_REF] for more details):

k λ def = |K λ | = n! 1 m 1 m 1 ! 2 m 2 m 2 ! • • • n mn m n ! .
Thus there is a natural one to one correspondence between partitions of n and conjugacy classes of S n .

Configurations as permutations

Let C be a configuration of a keyword query q = {k 1 , k 2 , • • • , k N } on a database D with a vocabulary V D given by

k 1 → b j 1 , k 2 → b j 2 , • • • , k N → b j N ,
we identify it with π ∈ S |V D | given by:

• π(i) = j i for all i ≤ N , • for each z ≤ N with N < π(z) ≤ |V D |, we call i = π(z)
and define π(i) in order to obtain the smallest cycle containing z. For each N < i ≤ |V D | not obtainned previously, we define π(i) = i. Equivalently:

-For each j ≤ N such that there is no i

≤ N with π(i) = j, if π(j), π 2 (j), • • •, π m-1 (j) are all ≤ N but N < π m (j) ≤ |V D |, we call i = π m (j)
and define π(i) = π m+1 (j) = j obtainning a cycle of length ≤ N + 1 in which only one value is bigger than N .

-For each N < i ≤ |V D | such that there is no j ≤ N with π(j) = i, we define π(i) = i obtaining a fixedpoint. All this points will be fixedpoints so, if

|V D | is bigger enough (|V D | ≥ 2 * N ),
• π(1) = 4, π(2) = 7, π(3) = 6, π(4) = 1, π(5) = 3 • Since 2 ≤ 5 such that there is no i ≤ 5 with π(i) = 2, π(2) = 7 and 7 > 5, then π(7) = π 2 (2) = 2.
• Since 5 ≤ 5 such that there is no i ≤ 5 with π(i) = 5, π(5) = 3 with 3 ≤ 5 and π 2 (5) = π(3) = 6 with 6 > 5, then π(6) = π 3 (5) = 5.

• Since 8 > 5 such that there is no i ≤ 5 with π(i) = 8, then π(8) = 8.

We have a 3-cycle [START_REF] Bourgeois | An extension of the munkres algorithm for the assignment problem to rectangular matrices[END_REF][START_REF] Leon | SQL: A Complete Reference[END_REF][START_REF] Fulton | Young tableaux: with applications to representation theory and geometry[END_REF], two 2-cycles (1, 4), (2, 7) and a fixedpoint [START_REF] Sagan | The Symmetric Group. Representations, Combinatorial Algorithms, and Symmetric Funtions[END_REF], so the cycle notation is π = (3, 6, 5)(1, 4)(2, 7)(8).

The type is (1 1 , 2 2 , 3 1 , 4 0 , 5 0 , 6 0 , 7 0 , 8 0 ), corresponding to the partition of 8: λ = (3, 2, 2, 1).

k λ = 8! 2 2 •2!•3 = 1680, so the conjugacy class of π, K π = K λ , contains 1680 elements. Note 3.3 If π ∈ S |V D |
is a configuration of a keyword query q with N keywords on a database D with vocabulary V D , the type cycle of π is We have an equivalence relation between configurations through the conjugacy in S |V D | . In addition, this definition of configuration permits to order configurations through some orders that we can consider on partitions. These are two important reasons why explaining configurations as elements of the symmetric group opens up a way to explain top-k algorithms as combinatorial algorithms.

λ = (λ 1 , • • • , λ m , 1, • • • , 1) ⊢ |V D |, with λ i > 1 (1 ≤ i ≤ m) and m i=1 λ i ≤ m + N. Proof 3.4 Indeed, if π = c 1 c 2 • • • c r in cycle notation and it has k fixed- points, the type cycle of π is λ = (λ 1 , • • • , λ m , 1, • • • , 1), where λ i > 1 (1 ≤ i ≤ m) and r = m + k.

Matrix Representations of a Group

To stablish the orders needed to explain top-k algorithms as combinatorial algorithms, we need some previous results about group representations that are explained in this Section.

Matrix Representations and G-Modules

A matrix representation can be thought of as a way to model an abstract group with a concrete group of matrices.

Definition 4.1 A matrix representation of a group G [8] is a group homo- morphism X : G -→ GL d ,
where d is the degree, or dimension, of the representation, denoted by degX, GL d denotes the complex general linear group of degree d of all matrices X = (x i,j ) d×d ∈ M at d that are invertible with respect to multiplication and M at d denotes the set of all d×d matrices with entries in the complex numbers C.

Let G be a group and V be a vector space over the complex numbers of finite dimension. Let GL(V ) stand for the set of all invertible linear transformations of V to itself, called the general linear group of V . If dimV = d, then GL(V ) and GL d are isomorphic as groups. Definition 4.2 Let V be a vector space and G be a group, then V is a G-module if there is a group homomorphism

ρ : G -→ GL(V ).
Let G be a group of finite order n. We denote by C[G] the algebra of G over C; this algebra has a basis indexed by elements of G and most of the time we identify this bases with G. Each element in C[G] can be uniquely written in the form

c 1 g 1 + • • • + c n g n , c i ∈ C and multiplication in C[G] extends that in G.
Let V be a C-vectorial space and let ρ :

G -→ GL(V ) be a linear representation of G in V . For g ∈ G and v ∈ V set g • v ≡ ρ g (v).
By linearity this defines f • v for f ∈ C[G] and v ∈ V . Thus, V is endowed with the structure of a left G-module. Conversely such structure defines a linear representation of G in V .

An idea pervading all of science is that large structures can be understood by breaking them up into their smallest pieces. The same thing is true in representation theory. Some representations are built out of smaller ones, whereas others are indivisible. This is the distinction between reducible and irreducible representations.

V = W (1) ⊕ W (2) ⊕ • • • ⊕ W (k) ,
where each W (i) is an irreducible G-submodule of V .

Tableaux and Tabloids

We need something about irreducible representations of the symmetric group. We know that the number of such representatios is equal to the number of conjugacy classes, that is the number of partitions of n.

It may not be obvious how to associate an irreducible with each partition λ = (λ 1 , λ 2 , ..., λ l ) but it is easy to find a corresponding soubgroup S λ that is an isomorphic copy of

S λ 1 × S λ 2 × • • • × S λ l
inside S n . So, we can produce the right number of representations by including the trivial representation on each S λ up to S n .

If M λ is a module for the last representation, it is not irreducible. However, we will be able to find an ordering λ (1) , λ (2)

{t} = {t 1 |t 1 ∼ t},
where sh t = λ.

If λ = (λ 1 , λ 2 , • • • , λ l ) ⊢ n, then the number of tableaux in any given equivalence class is λ! def = λ 1 !λ 2 ! • • • λ l !. Thus the number of λ-tabloids is just n! λ! .
. Let t i,j stand for the entry of a λ-tableau t in position (i, j). Now π ∈ S n acts on a tableau t = (t i,j ) of shape λ ⊢ n as follows: In this case we say that M is generated by v.

Conclusions

We have provided a formal characterization for the configurations in terms of some elements in the symmetric group S n . We have shown that such a characterization allows us to reduce the number of configurations to check.

In addition, using the symmetric group it is possible to give an order between configurations. That is an important fact because in keyword based search we can obtain more than one configuration for the same keyword query.

Many results about representations of the symmetric group can be used in a purely combinatorial manner. Some top-k works [START_REF] Domnori | Top-k results using the hungarian algorithm[END_REF] uses a combinatorial algorithms, such as the Hungarian algorithm (also called Munkres assignment algorithm [START_REF] Bourgeois | An extension of the munkres algorithm for the assignment problem to rectangular matrices[END_REF]), to give the best answer for a for a keyword query in the context of information search. So, since the representations of the symmetric group can be used to obtain combinatorial algorithms, explaining configurations as a kind of elements of the symmetric group is a first step to formalize Keymantic as a combinatorial algorithm.

Example 3 . 2

 32 we will have at least |V D | -2 * N fixedpoints. Definition 3.1 A configuration C of a keyword query q with N keywords on a database D with vocabulary V D is a permutation π ∈ S |V D | such that each cycle of π contains no more than an element of value bigger than N (1 ≤ i ≤ r). Let be a keyword query q = {k 1 , k 2 , k 3 , k 4 , k 5 } and a database D with vocabulary V D = {b 1 , b 2 , b 3 , b 4 , b 5 , b 6 , b 7 , b 8 }, then N = 5 and |V D | = 8 and there are 8! (8-5)! = 6720 configurations. The configuration k 1 → b 4 , k 2 → b 7 , k 3 → b 6 , k 4 → b 1 , k 5 → b 3 can be extended to the following permutation π ∈ S 8 :

  Since each cycle of π, c i , contains no more than an element of value bigger than N and we have |V D | -N elements bigger than N , π has at least |V D | -N cycles. Thus r ≥ |V D | -N . Consecuently, since |V D | = m i=1 λ i + k, we have m i=1 λ i ≤ m + N .

Definition 4 . 3

 43 Let V be a G-module. A submodule of V , or G-invariant subspace, is a subspace W that is closed under the action of G, i.e., w ∈ W ⇒ gw ∈ W ∀g ∈ G. Definition 4.4 A nonzero G-module V is reducible if it contains a non trivial submodule W ; otherwise, V is said to be irreducible.

Theorem 4 . 5 (

 45 Maschke's Theorem) Let G be a finite group and let V be a nonzero G-module, then

  πt = (π(t i,j )). This induces an action on tabloids by letting π{t} = {πt}. Definition 4.10 Suppose λ ⊢ n. LetM λ = C{{t 1 }, • • • , {t k }}, the permutation module corresponding to λ, where {t 1 }, • • • , {t k } is a complete list of λ-tabloids. Definition 4.11 Any G-module M is cyclic if there is a v ∈ M such that M = CGv,where Gv = {gv | g ∈ G}.

  , • • • of all partitions of n with nice properties. To build the modules M Definition 4.7 A Young tableau of shape λ ⊢ n, or λ-tableau, [5] is an array t obtained by replacing the dots of the Ferrers diagram of λ with the numbers 1, 2, • • •, n bijectively. Alternatively, we write sh t = λ.There are n! Young tableaux for any shape λ ⊢ n. Two λ-tableaux t 1 and t 2 are row equivalent,t 1 ∼ t 2 ,if corresponding rows of the two tableaux contain the same elements.Definition 4.9 A tabloid of shape λ, or λ-tabloid, is

	Definition 4.8

λ first we need: Definition 4.6 The Ferrers diagram, or shape, of λ = (λ 1 , λ 2 , ..., λ l ) ⊢ n is an array of n dots having l left-justified rows with row i containing λ i dots for 1 ≤ i ≤ l. The dot in row i and column j has coordinates (i, j), as in a matrix.

 Proposition 4.12 If λ ⊢ n, then [START_REF] Sagan | The Symmetric Group. Representations, Combinatorial Algorithms, and Symmetric Funtions[END_REF] M λ is cyclic, generated by any given λ-tabloid. In addition,

the number of λ-tabloids.

Example 4.13 Let λ = (3, 2) ⊢ 5. The Ferrers diagram, or shape, of λ is

Some Young tableaux of shape λ, or a λ-tableaux, are

A tabloid of shape λ, or λ-tabloid, is There are 5! 3! • 2! = 10 λ-tabloids.

The permutation module corresponding to

The action of (1, 3, 5)(2)(4) ∈ S 5 on t 1 is:

and the action of (1, 3, 5)(2)(4) ∈ S 5 on {t 1 }:

Dominance and Lexicographic ordering

We consider two important orderings [START_REF] Sagan | The Symmetric Group. Representations, Combinatorial Algorithms, and Symmetric Funtions[END_REF] on partitions of n.

are partitions of n:

• λ dominates µ, written λ µ, if

), then we take λ i (respectively, µ i ) to be zero.

• λ < µ in lexicographic order if, for some index i, λ j = µ j for j < i and

The dominance order is partial and the lexicographic is total. The lexicographic order is a refinement of the dominance order in this sense:

Intuitively, λ is greater than µ in the dominance order if the Ferrers diagram of λ is short and fat but the one for µ is long and skinny.

. In dominance order:

• (2, 2, 2, 1, 1) (2, 2, 1, 1, 1, 1) (2, 1, 1, 1, 1, 1, 1) (1, 1, 1, 1, 1, 1, 1, 1).

• (3, 1, 1, 1, 1, 1) and (2, 2, 2, 1, 1) are incomparables but (3, 2, 1, 1, 1) (2, 2, 2, 1, 1) and (3, 1, 1, 1, 1, 1) (2, 2, 1, 1, 1, 1).