Staircase visibility and computation of kernels

Let be some set of orientations, that is, . We consider the consequences of defining visibility based on curves that are monotone with respect to the orientations in . We call such curves -staircases. Two points p andq in a polygonP are said to -see each other if an -staircase fromp toq exists that is completely contained inP. The -kernel of a polygonP is then the set of all points which -see all other points. The -kernel of a simple polygon can be obtained as the intersection of all {}-kernels, with . With the help of this observation we are able to develop an algorithm to compute the -kernel of a simple polygon, for finite . We also show how to compute theexternal -kernel of a polygon in optimal time . The two algorithms are combined to compute the ( -kernel of a polygon with holes in time .This work was supported by the Deutsche Forschungsgemeinschaft under Grant No. Ot 64/5-4 and the Natural Sciences and Engineering Research Council of Canada and Information Technology Research Centre of Ontario.     

Calculation of associated functions for rational modified weight functions

Let be a sequence of polynomials orthogonal with respect to a measure dω on the real line and the sequence of their associated functions (they are essentially the Hilbert transforms of these polynomials). We show how to get associated functions Q _n ^[m,l] if the measure dω changes to , where Φ_m and ϕ _l are polynomials of degree m resp.l. The results can be used for example to construct Gaussian quadrature rules for rational modified weight functions.     

Finding tree patterns consistent with positive and negative examples using queries

This paper is concerned with the problem of finding a hypothesis in consistent with given positive and negative examples. The hypothesis class consists of all sets of at most two tree patterns and represents the class of unions of at most two tree pattern languages. Especially, we consider the problem from the point of view of the consistency problem for . The consistency problem is a problem for deciding whether there exists a consistent hypothesis with given positive and negative examples within some fixed hypothesis space. Efficient solvability of that problem is closely related to the possibility of efficient machine learning or machine discovery. Unfortunately, however, the consistency problem is known to be NP-complete for many hypothesis spaces. In this paper, the problem for the class is also shown to be NP-complete. In order to overcome this computational hardness, we try to use additional information obtained by making queries. First, we give an algorithm that, using restricted subset queries, solves the consistency problem for in time polynomial in the total size of given positive and negative examples. Next, we show that each subset query made by the algorithm can be replaced by several membership queries under some condition on a set of function symbols. As a result, we have that the consistency problem for is solved in polynomial time using membership queries. This revised version was published online in June 2006 with corrections to the Cover Date.     

L’integrazione numerica di una classe di integrali utili nei calcoli quantomeccanici

The numerical integration of integrals of the type dx is carried out through an approximate quadrature formula of the Gauss type where the abscissasx _i and the weighting coefficientsA _i are evaluated with the requirement that the above formula be exact when thef(x) are polynomials of the highest possible degree.      

A semantically complete extension sequence of the system $$\mathcal{L}^* $$

In this paper, the method of well-combined semantics and syntax proposed by Pavelka is applied to the research of the propositional calculus formal system . The partial constant values are taken as formulas, formulas are fuzzified in two manners of semantics and syntax, and inferring processes are fuzzified. A sequence of new extensions { } of the system is proposed, and the completeness of is proved.     

Upon some continuous prediction algorithms. I

Three difference-differential processes operating upon an initial value function Φ (μ) and yielding a sequence of approximations to are described. The processes are confluent analogues of an algorithm related to Romberg's extrapolation procedure, of the π-algorithm, and of the ε-algorithm. It is shown that these processes can be modified to yield approximations to the integral , and that in certain circumstances this integral can be evaluated by a process of repeated differentiation involving the function ψ(μ). Discrete algorithms for approximating , for which it is assnmed, that values of the successive derivatives of the function Φ (μ) are available, are described. It is shown that these algorithms can be applied to the evaluation of the integral , it being assumed that the values of the successive derivatives of the function ψ(μ) are available. A number of examples in which closed expressions for the transformed estimates can be derived are discussed. Algol procedures for implementing the discrete algorithms are given In Memoriam H. Rutishauser     

Lange and Wiehagen's pattern language learning algorithm: An average-case analysis with respect to its total learning time

The present paper deals with the best-case, worst-case and average-case behavior of Lange and Wiehagen's (1991) pattern language learning algorithm with respect to its total learning time. Pattern languages have been introduced by Angluin (1980) and are defined as follows: Let be any non-empty finite alphabet containing at least two elements. Furthermore, let be an infinite set of variables such that . Patterns are non-empty strings over . L(π), the language generated by pattern π, is the set of strings which can be obtained by substituting non-null strings from for the variables of the pattern π. Lange and Wiehagen's (1991) algorithm learns the class of all pattern languages in the limit from text. We analyze this algorithm with respect to its total learning time behavior, i.e., the overall time taken by the algorithm until convergence. For every pattern π containing k different variables it is shown that the total learning time is in the best-case and unbounded in the worst-case. Furthermore, we estimate the expectation of the total learning time. In particular, it is shown that Lange and Wiehagen's algorithm possesses an expected total learning time of with respect to the uniform distribution. This revised version was published online in June 2006 with corrections to the Cover Date.     

Congruences et Automorphismes des Automates Finis

Summary We study a class of congruences of strongly connected finite automata, called the group congruences, which may be defined in this way: every element fixing any class of the congruence induces a permutation on this class. These congruences form an ideal of the lattice of all congruences of the automaton and we study the group associated with the maximal group congruence (maximal induced group) with respect to the Suschkevitch group of the transition monoid of . The transitivity equivalence of the subgroups of the automorphism group of are found to be the group congruences associated with regular groups, which form also in ideal of the lattice of congruences of . We then characterize the automorphism group of with respect to the maximal induced group. As an application, we show that, given a group G and an automaton , there exists an automaton whose automorphism group is isomorphic to G and such that the quotient by the automorphism congruence is .     

The computational complexity of recognizing permutation functions

Let be a finite field withq elements and a rational function over . No polynomial-time deterministic algorithm is known for the problem of deciding whetherf induces a permutation on . The problem has been shown to be in co-R co-NP, and in this paper we prove that it is inR NP and hence inZPP, and it is deterministic polynomial-time reducible to the problem of factoring univariate polynomials over . Besides the problem of recognizing prime numbers, it seems to be the only natural decision problem inZPP unknown to be inP. A deterministic test and a simple probabilistic test for permutation functions are also presented.     

Formule di quadratura con funzione di influenza di segno costante

Sommario Si espongono tre procedimenti per costruire formule di quadratura, relative ad un integrale col pesog(x)≥0, che abbiano la funzione di influenza di segno costante.

---

Summary Three procedures are exposed to construct quadrature formulae, relative to an integral with a weightg(x)≥0, whose influence function doesn't change sign.

     

Calcolo approssimato per difetto e per eccesso di integrali

Sommario Viene fornito un metodo in cui si fa uso di formule di quadratura generalizate per il calcolo approssimato per difetto e per eccesso dell'integrale ..u(x)dx doveu(x)∈AC ⁿ⁻¹ [0,1];u ⁽ⁿ⁾ (x) è limitata inferiormente;p(x)=1 oppurep(x)∈L [0, 1],p(x)>-0 e . Vengono poi dati alcuni esempi numerici.

---

A method, using generalized quadrature formulae, is given for approximate evaluation from below and above of whereu(x)∈A C ⁿ⁻¹ [0,1],u ⁽ⁿ⁾ (x) lower bounded,p(x)=1 orp(x)∈L [0,1],p(x)≥0, . Some numerical examples are given.

---

---

Lavoro eseguito nell'ambito del gruppo di ricerca G.N.A.F.A. del C.N.R.     

Universal asynchronous iterative arrays of Mealy automata

Summary Asynchronous two-dimensional iterative arrays of automata will be introduced where the underlying automata are not of Moore-type but of Mealy-type. We will prove that there exists a Mealy automaton, , with only two states and one input and output for each of its four distinguished directions, such that any given Mealy-automaton can be realized by an iterative array with only for its component-machines. It is known that loop-free nets cannot be as powerful as Mealy automata; however, we will show that any Mealy automaton can be realized by a network, N, with very restrictive component machines, where no signal may pass a loop in N. Using this fact asynchronous iterative arrays can be built up with one component machine, such that any given Mealy automaton can be realized under the restriction that no signal passes a loop more than once. contains only four states and one input and output for each direction.     

Sulla ricerca dei digrafi fortemente connessi aventi uno stesso grafo di supporto e di lunghezza generalizzata minima o massima

Sunto Assegnato un grafo finitoG ₀, notiamo con la famiglia dei digrafiG aventiG ₀ come grafo di supporto. E' noto che alla famiglia appartengono digrafi fortemente conuessi (f. c.) se e solo seG ₀ è connesso e ogni sno spigolo appartiene a qualche ciclo. Nel presente lavoro iudaghiamo sulla struttura dei digrafi fortemente connessi di una assegnata famiglia e dimostriamo come tali digrafi si possono costruire tutti a partire da uno di essi (costruito a sua volta utilizzando un algoritmo di B. Roy) mediante l'applicazione di un numero finito di trasformazioni elementari opportunamente introdotte. Se immaginiamo il grafoG ₀ come rappresentazione di una certa rete stradale, dobbiamo interpretare ogni digrafo di come un possibile orientamento a sensi unici di tutte le strade della rete. A ciascuno dei due possibili orientamenti degli spigoli della reteG ₀ è possibile associare un numero reale esprimente il costo oppure l'utilità di quell'orientamento: in tal modo ad ogni orientamento a sensi unici delle strade della rete risulta associato un costo complessivo oppure un utile complessivo. Il problema di orientare in modo ottimo gli spigoli delle reteG ₀, compatibilmente con i vincoli di percorribilità dell'intera rete, si traduce nella ricerca dei digrafi f. c. di a cui è associata una lunghezza generalizzata minima oppure massima. Noi affrontiamo tale problema e presentiamo una condizione necessaria e sufficiente di ottimo che permette di costruire mediante un opportuno algoritmo i digrafi fortemente connessi di di lunghezza generalizzata minima oppure massima.

---

Given a finite graphG ₀, let be the family of digraphs that haveG ₀ as a supporting graph. It is a well established fact that contains strongly connected (s. c.) digraphs if and only ifG ₀ is connected, and if every edge ofG ₀ belongs to one or more cycles. In the present work the structure of s. c. digraphs of a given family is investigated. It is also proved that all such digraphs can be constructed from one of them (that itself is constructed by an algorithm of B. Roy), with a finite number of appropriate elementary transformations. If a graphG ₀ represents a given road network, every digraph in can be interpreted as a possible one-way orientation of all the roads in the network. One can associate with each of the orientations of the edges ofG ₀ a real number representing the cost or the gain of such an orientation: thus, with every one-way system in the network is associated a cumulative cost or a cumulative gain. The problem of the optimal orientation of the edges ofG ₀, while respecting the constraints on the viability of the entire network, becomes the search of s. c. digraphs in associated with optimal generalized lengtht. A necessary and sufficient condition for optimality is presented, that leads to the construction, by means of an appropriate algorithm, of s. c. diagraphs in with optimal generalized lenght.

     

Algorithms and optimality of scheduling soft aperiodic requests in fixed-priority preemptive systems

In this paper, we investigate the problem of scheduling soft aperiodic requests in systems where periodic tasks are scheduled on a fixed-priority, preemptive basis. First, we show that given any queueing discipline for the aperiodic requests, no scheduling algorithm can minimize the response time of every aperiodic request and guarantee that the deadlines of the periodic tasks are met when the periodic tasks are scheduled on a fixed-priority, preemptive basis. We then develop two algorithms: Algorithm is locally optimal in that it minimizes the response time of the aperiodic request at the head of the aperiodic service queue. Algorithm is globally optimal in that it completes the current backlog of work in the aperiodic service queue as early as possible.     

Su di una equazione funzionale della programmazione dinamica

Sommario Un problema economico di programmazione degli interventi conduce allo studio dell'equazione funzionale . Essa non rientra nelle classi di equazioni della programmazione dinamica per le quali attualmente si conoscono teoremi di esistenza ed unicità. Sotto condizioni naturali per la funzionek (x) si dimostrano esistenza ed unicità di una soluzione ϕ (x) tendente a zero perx tendente a zero. Si considerano alcuni casi particolari e si presenta un procedimento di approssimazioni successive.

---

An economic problem of development programming leads to the study of the functional equation . It does not belong to any class of dynamic programming equations for which at pressent existence and uniqueness theorems are known. Under proper requirements for the functionk(x), existence and uniquenness of a solution ϕ(x) convergent to 0 whenx→0 is prooved. Some particular cases are considered and an iterative method of successive approximations is given.

     

Structural properties for feasibly computable classes of type two

This paper treates classes in the polynomial hierarchy of type two, , that were first developed by Townsend as a natural extension of the Meyer-Stockmeyer polynomial hierarchy in complexity theory. For these classes, it is discussed whether each of them has the extension property and the three recursion-theoretic properties: separation, reduction, and pre-wellordering. This paper shows that every 0$$ " align="middle" border="0"> , lacks the pre-wellordering property by using a probabilistic argument on constant-depth Boolean circuits. From the assumption NP = coNP it follows by a pruning argument that has the separation and extension properties.     

Algorithmic properties of maximal orders in simple algebras over Q

This paper addresses an algorithmic problem related to associative algebras. We show that the problem of deciding if the index of a given central simple algebra over an algebraic number field isd, whered is a given natural number, belongs to the complexity classN P co N P. As consequences, we obtain that the problem of deciding if is isomorphic to a full matrix algebra over the ground field and the problem of deciding if is a skewfield both belong toN P co N P. These results answer two questions raised in [25]. The algorithms and proofs rely mostly on the theory of maximal orders over number fields, a noncommutative generalization of algebraic number theory. Our results include an extension to the noncommutative case of an algorithm given by Huang for computing the factorization of rational primes in number fields and of a method of Zassenhaus for testing local maximality of orders in number fields.     

An analytic approach to the height of binary search trees

By using analytic tools it is shown that the expected value of the heightH _n of binary search trees of sizen is asymptotically given by EH _n =c logn+ (log logn) and its variance by VH _n = ((log logn)²), wherec=4.31107 …. The same bounds have been obtained by Devroye and Reed [3] by completely different methods. Dedicated to Philippe Flajolet on the occasion of his 50th birthday This research was supported by the Austrian Science Foundation FWF, Grant P10187-MAT. Online publication September 22, 2000.     

Lower Bound Methods and Separation Results for On-Line Learning Models

We consider the complexity of concept learning in various common models for on-line learning, focusing on methods for proving lower bounds to the learning complexity of a concept class. Among others, we consider the model for learning with equivalence and membership queries. For this model we give lower bounds on the number of queries that are needed to learn a concept class in terms of the Vapnik-Chervonenkis dimension of , and in terms of the complexity of learning with arbitrary equivalence queries. Furthermore, we survey other known lower bound methods and we exhibit all known relationships between learning complexities in the models considered and some relevant combinatorial parameters. As it turns out, the picture is almost complete. This paper has been written so that it can be read without previous knowledge of Computational Learning Theory.