Algebraic Theory of Minimal Nondeterministic Finite Automata with Applications

Since the 1950s, the theory of deterministic and nondeterministic finite automata (DFAs and NFAs, respectively) has been a cornerstone of theoretical computer science. In this dissertation, our main object of study is minimal NFAs. In contrast with minimal DFAs, minimal NFAs are computationally challenging: first, there can be more than one minimal NFA recognizing a given language; second, the problem of converting an NFA to a minimal equivalent NFA is NP-hard, even for NFAs over a unary alphabet. Our study is based on the development of two main theories, inductive bases and partials, which in combination form the foundation for an incremental algorithm, ibas, to find minimal NFAs. An inductive basis is a collection of languages with the property that it can generate (through union) each of the left quotients of its elements. We prove a fundamental characterization theorem which says that a language can be recognized by an n-state NFA if and only if it can be generated by an n-element inductive basis. A partial is an incompletely-specified language. We say that an NFA recognizes a partial if its language extends the partial, meaning that the NFA's behavior is unconstrained on unspecified strings; it follows that a minimal NFA for a partial is also minimal for its language. We therefore direct our attention to minimal NFAs recognizing a given partial. Combining inductive bases and partials, we generalize our characterization theorem, showing that a partial can be recognized by an n-state NFA if and only if it can be generated by an n-element partial inductive basis. We apply our theory to develop and implement ibas, an incremental algorithm that finds minimal partial inductive bases generating a given partial. In the case of unary languages, ibas can often find minimal NFAs of up to 10 states in about an hour of computing time; with brute-force search this would require many trillions of years.

Problems in number theory and hyperbolic geometry

In the first part of this thesis we generalize a theorem of Kiming and Olsson concerning the existence of Ramanujan-type congruences for a class of eta quotients. Specifically, we consider a class of generating functions analogous to the generating function of the partition function and establish a bound on the primes ℓ for which their coefficients c(n) obey congruences of the form c(ℓn + a) ≡ 0 (mod ℓ). We use this last result to answer a question of H.C. Chan. In the second part of this thesis [S2] we explore a natural analog of D. Calegari’s result that there are no hyperbolic once-punctured torus bundles over S^1 with trace field having a real place. We prove a contrasting theorem showing the existence of several infinite families of pairs (−χ, p) such that there exist hyperbolic surface bundles over S^1 with trace field of having a real place and with fiber having p punctures and Euler characteristic χ. This supports our conjecture that with finitely many known exceptions there exist such examples for each pair ( −χ, p).

On the duration of negative surplus

Doutoramento em Matemática

On Some Unifications Arising from the MIMO Rician Shadowed Model

This paper shows that the proposed Rician shadowed model for multi-antenna communications allows for the unification of a wide set of models, both for multiple-input multiple-output (MIMO) and single- input single-output (SISO) communications. The MIMO Rayleigh and MIMO Rician can be deduced from the MIMO Rician shadowed, and so their SISO counterparts. Other more general SISO models, besides the Rician shadowed, are included in the model, such as the κ-μ, and its recent generalization, the κ-μ shadowed model. Moreover, the SISO η-μ and Nakagami-q models are also included in the MIMO Rician shadowed model. The literature already presents the probability density function (pdf) of the Rician shadowed Gram channel matrix in terms of the well-known gamma- Wishart distribution. We here derive its moment generating function in a tractable form. Closed- form expressions for the cumulative distribution function and the pdf of the maximum eigenvalue are also carried out.

Semi-Classical Mechanics in Phase Space: A Study of Wigner's Function

We explore the semi-classical structure of the Wigner functions ($\Psi $(q, p)) representing bound energy eigenstates $|\psi \rangle $ for systems with f degrees of freedom. If the classical motion is integrable, the classical limit of $\Psi $ is a delta function on the f-dimensional torus to which classical trajectories corresponding to ($|\psi \rangle $) are confined in the 2f-dimensional phase space. In the semi-classical limit of ($\Psi $ ($\hslash $) small but not zero) the delta function softens to a peak of order ($\hslash ^{-\frac{2}{3}f}$) and the torus develops fringes of a characteristic 'Airy' form. Away from the torus, $\Psi $ can have semi-classical singularities that are not delta functions; these are discussed (in full detail when f = 1) using Thom's theory of catastrophes. Brief consideration is given to problems raised when ($\Psi $) is calculated in a representation based on operators derived from angle coordinates and their conjugate momenta. When the classical motion is non-integrable, the phase space is not filled with tori and existing semi-classical methods fail. We conjecture that (a) For a given value of non-integrability parameter ($\epsilon $), the system passes through three semi-classical regimes as ($\hslash $) diminishes. (b) For states ($|\psi \rangle $) associated with regions in phase space filled with irregular trajectories, ($\Psi $) will be a random function confined near that region of the 'energy shell' explored by these trajectories (this region has more than f dimensions). (c) For ($\epsilon \neq $0, $\hslash $) blurs the infinitely fine classical path structure, in contrast to the integrable case ($\epsilon $ = 0, where $\hslash $ )imposes oscillatory quantum detail on a smooth classical path structure.

Semi-weight function method on computation of stress intensity factors in dissimilar materials

Semi-weight function method is developed to solve the plane problem of two bonded dissimilar materials containing a crack along the bond. From equilibrium equation, stress and strain relationship, conditions of continuity across interface and free crack surface, the stress and displacement fields were obtained. The eigenvalue of these fields is lambda. Semi-weight functions were obtained as virtual displacement and stress fields with eigenvalue-lambda. Integral expression of fracture parameters, K-I and K-II, were obtained from reciprocal work theorem with semi-weight functions and approximate displacement and stress values on any integral path around crack tip. The calculation results of applications show that the semi-weight function method is a simple, convenient and high precision calculation method.

The Characteristics of Semi-Cokes --The Solid Residues from Coal Partial Gasification

In this paper the proximate analysis and ultimate analysis of sulfur in different semi-cokes generated from Rizhao bituminous coal and Beijing anthracite under different temperatures is done. Also the tendency of the contents of volatile, ash, fixed carbon and sulfur in different semi-cokes along with the different preparation temperatures is studied. Then the combustion experiment of semi-cokes in the drop-tube furnace system was carried out, and the kinetic parameters of different semi-cokes ware calculated.

Semi-intensive shrimp farming system of Kerala, India: a production function analysis

An analysis of the factor-product relationship in the semi-intensive shrimp farming system of Kerala, farm basis and hectare basis, we are attempted and the results reported in this paper. The Cobb-Douglas model, in which the physical relationship between input and output is estimated, and the marginal analysis then employed to evaluate the producer behaviour, was used for the analysis. The study was based on empirical data collected during November 1994 to May 1996, covering three seasons, from 21 farms spread over Alappuzha, Ernakulam and Kasaragod districts of the state. The sample covered a total area of 61.06 ha. Of the 11 explanatory variables considered in the model, the size of the farm, casual labour and chemical fertilizers were found statistically significant. It was also observed that the factors such as age of pond, experience of the farmer, feed, miscellaneous costs, number of seed stocked and skilled labour contributed positively to the output. The estimated industry production function exhibited unitary economies of scale. The estimated mean output was 3937 kg/ha. The test of multi-co-linearity showed that there is no problem of dominant variable. On the basis of the marginal product and the given input-output prices, the optimum amounts of seed, feed and casual labour were estimated. They were about 97139 seed, 959 kg of feed and 585 man-days of casual labour per farm. This indicated the need for reducing the stocking density and amount of feed from the present levels, in order to maximise profit. Based on the finding of the study, suggestions for improving the industry production function are proposed.

The reasons behind the progression in PISA scores: An education production function approach using semi-parametric techniques

Research Masters

Efficient estimation using the characteristic function : theory and applications with high frequency data

The attached file is created with Scientific Workplace Latex