In this thesis, we cover the general topic of state complexity. In particular, we examine the bounds on the state complexity of some different representations of regular languages. As well, we consider the state complexity of the operation root(<i>L</i>). We give quick treatment of the deterministic state complexity bounds for nondeterministic finite automata and regular expressions. This includes an improvement on the worst-case lower bound for a regular expression, relative to its alphabetic length. The focus of this thesis is the study of the increase in state complexity of a regular language <i>L</i> under the operation root(<i>L</i>). This operation requires us to examine the connections between abstract algebra and formal languages. We present results, some original to this thesis, concerning the size of the largest monoid generated by two elements. Also, we give good bounds on the worst-case state complexity of root(<i>L</i>). In turn, these new results concerning root(<i>L</i>) allow us to improve previous bounds given for the state complexity of two-way deterministic finite automata.

In this thesis, we cover the general topic of state complexity. In particular, we examine the bounds on the state complexity of some different representations of regular languages. As well, we consider the state complexity of the operation root(<i>L</i>). We give quick treatment of the deterministic state complexity bounds for nondeterministic finite automata and regular expressions. This includes an improvement on the worst-case lower bound for a regular expression, relative to its alphabetic length. The focus of this thesis is the study of the increase in state complexity of a regular language <i>L</i> under the operation root(<i>L</i>). This operation requires us to examine the connections between abstract algebra and formal languages. We present results, some original to this thesis, concerning the size of the largest monoid generated by two elements. Also, we give good bounds on the worst-case state complexity of root(<i>L</i>). In turn, these new results concerning root(<i>L</i>) allow us to improve previous bounds given for the state complexity of two-way deterministic finite automata.

Garantir le fonctionnement correct des systèmes informatisés est un enjeu chaque jour plus important. La vérification formelle est un ensemble de techniquespermettant d’établir la correction d’un modèle mathématique du système par rapport à des propriétés exprimées dans un langage formel.Le "Regular model checking" est une technique bien connuede vérification de systèmes infinis. Elle manipule des ensembles infinis de configurations représentés de façon symbolique. Le "Regular model checking" de systèmes à canaux non fiables (LCS) soulève des questions fondamentales de décision et de complexité concernant l’ordre sous-mot qui modélise la perte de messages. Nous abordons ces questions et résolvons un problème ouvert sur l’index de la congruence de Simon pour les langages testables par morceaux.L’accessibilité pour les LCS est décidable mais de complexité F_{omega^omega} très élevée, bien au delà des complexités primitives récursives. Plusieurs problèmes de complexité équivalente ont été découverts récemment, par exemple dans la vérification de mémoire faibles ou de logique temporelle métrique. Le problème de plongement de Post (PEP) est une abstraction de l’accessibilité des LCS, lui aussi de complexité F_{omega^omega}, et qui nous sert de base dans la définition d’une classe de complexité correspondante. Nous proposons une généralisation commune aux deux variantes existantes de PEP et donnons une preuve de décidabilité simplifiée. Ceci permet d’étendre le modèle des systèmes à canaux unidirectionnels (UCS) par des tests simples tout en préservant la décidabilité de l’accessibilité. / The increasing use of software and automated systems has made it important to ensure their correct behaviour. Formal verification is the technique that establishes correctness of a system or a mathematical model of the system with respect to properties expressed in a formal language.Regular model checking is a common technique for verification of infinite-state systems - it represents infinite sets of configurations symbolically in a finite manner and manipulates them using these representations. Regular model checking for lossy channel systems brings up basic automata-theoretic questions concerning the subword relation on words which models the lossiness of the channels. We address these state complexity and decision problems, and also solve a long-standing problem involving the index of the Simon's piecewise-testability congruence.The reachability problem for lossy channel systems (LCS), though decidable, has very high F_{omega^omega} complexity, well beyond primitive-recursive. In recent times several problems with this complexity have been discovered, for example in the fields of verification of weak memory models and metric temporal logic. The Post Embedding Problem (PEP) is an algebraic abstraction of the reachability problem on LCS, with the same complexity, and is our champion for a "master" problem for the class F_{omega^omega}. We provide a common generalization of two known variants of PEP and give a simpler proof of decidability. This allows us to extend the unidirectional channel system (UCS) model with simple channel tests while having decidable reachability.

The syntactic complexity of a regular language is the cardinality of its syntactic semigroup. The syntactic complexity of a subclass of the class of regular languages is the maximal syntactic complexity of languages in that class, taken as a function of the state complexity n of these languages. We study the syntactic complexity of suffix-, bifix-, and factor-free regular languages, star-free languages including three subclasses, and R- and J-trivial regular languages. We found upper bounds on the syntactic complexities of these classes of languages. For R- and J-trivial regular languages, the upper bounds are n! and ⌊e(n-1)!⌋, respectively, and they are tight for n >= 1. Let C^n_k be the binomial coefficient ``n choose k''. For monotonic languages, the tight upper bound is C^{2n-1}_n. We also found tight upper bounds for partially monotonic and nearly monotonic languages. For the other classes of languages, we found tight upper bounds for languages with small state complexities, and we exhibited languages with maximal known syntactic complexities. We conjecture these lower bounds to be tight upper bounds for these languages. We also observed that, for some subclasses C of regular languages, the upper bound on state complexity of the reversal operation on languages in C can be met by languages in C with maximal syntactic complexity. For R- and J-trivial regular languages, we also determined tight upper bounds on the state complexity of the reversal operation.

The syntactic complexity of a regular language is the cardinality of its syntactic semigroup. The syntactic complexity of a subclass of the class of regular languages is the maximal syntactic complexity of languages in that class, taken as a function of the state complexity n of these languages. We study the syntactic complexity of suffix-, bifix-, and factor-free regular languages, star-free languages including three subclasses, and R- and J-trivial regular languages. We found upper bounds on the syntactic complexities of these classes of languages. For R- and J-trivial regular languages, the upper bounds are n! and ⌊e(n-1)!⌋, respectively, and they are tight for n >= 1. Let C^n_k be the binomial coefficient ``n choose k''. For monotonic languages, the tight upper bound is C^{2n-1}_n. We also found tight upper bounds for partially monotonic and nearly monotonic languages. For the other classes of languages, we found tight upper bounds for languages with small state complexities, and we exhibited languages with maximal known syntactic complexities. We conjecture these lower bounds to be tight upper bounds for these languages. We also observed that, for some subclasses C of regular languages, the upper bound on state complexity of the reversal operation on languages in C can be met by languages in C with maximal syntactic complexity. For R- and J-trivial regular languages, we also determined tight upper bounds on the state complexity of the reversal operation.

Modern applications of XML use automata operating on unranked trees. A common definition of tree automata operating on unranked trees uses a set of vertical states that define the bottom-up computation, and the transitions on vertical states are determined by so called horizontal languages recognized by finite automata on strings. The bottom-up computation of an unranked tree automaton may be either deterministic or nondeterministic, and further variants arise depending on whether the horizontal string languages defining the transitions are represented by DFAs or NFAs. There is also an alternative syntactic definition of determinism introduced by Cristau et al. It is known that a deterministic tree automaton with the smallest total number of states does not need to be unique nor have the smallest possible number of vertical states. We consider the question by how much we can reduce the total number of states by introducing additional vertical states. We give an upper bound for the state trade-off for deterministic tree automata where the horizontal languages are defined by DFAs, and a lower bound construction that, for variable sized alphabets, is close to the upper bound. We establish upper and lower bounds for the state complexity of conversions between different types of deterministic and nondeterministic unranked tree automata. The bounds are, usually, tight for the numbers of vertical states. Because a minimal deterministic unranked tree automaton need not be unique, establishing lower bounds for the number of horizontal states, that is, the combined size of DFAs used to define the horizontal languages, is challenging. Based on existing lower bound results for unambiguous finite automata we develop a lower bound criterion for the number of horizontal states. We consider the state complexity of operations on regular unranked tree languages. The concatenation of trees can be defined either as a sequential or a parallel operation. Furthermore, there are two essentially different ways to iterate sequential concatenation. We establish tight state complexity bounds for concatenation-like operations. In particular, for sequential concatenation and bottom-up iterated concatenation the bounds differ by an order of magnitude from the corresponding state complexity bounds for regular string languages. / Thesis (Ph.D, Computing) -- Queen's University, 2012-01-04 14:48:02.916

No description available.