Explore the vast range of titles available.

The idea behind this book is to provide the mathematical foundations for assessing modern developments in the Information Age. It deepens and complements the basic concepts, but it also considers instructive and more advanced topics. The treatise starts with a general chapter on algebraic structures; this part provides all the necessary knowledge for the rest of the book. The next chapter gives a concise overview of cryptography. Chapter 3 on number theoretic algorithms is important for developping cryptosystems, Chapter 4 presents the deterministic primality test of Agrawal, Kayal, and Saxena. The account to elliptic curves again focuses on cryptographic applications and algorithms. With combinatorics on words and automata theory, the reader is introduced to two areas of theoretical computer science where semigroups play a fundamental role.The last chapter is devoted to combinatorial group theory and its connections to automata. Contents: Algebraic structures Cryptography Number theoretic algorithms Polynomial time primality test Elliptic curves Combinatorics on words Automata Discrete infinite groups

We introduce the notion of idempotent variables for studying equations in inverse monoids. It is proved that it is decidable in singly exponential time (DEXPTIME) whether a system of equations in idempotent variables over a free inverse monoid has a solution. Moreover the problem becomes hard for DEXPTIME, as soon as the quotient group of the free inverse monoid has rank at least two. The upper bound is proved by a direct reduction to solve language equations with one-sided concatenation and a known complexity result by Baader and Narendran (J. Symb. Comput. 31 , 277–305 2001 ). For the lower bound we show hardness for a restricted class of language equations. Decidability for systems of typed equations over a free inverse monoid with one irreducible variable and at least one unbalanced equation is proved with the same complexity upper-bound. Our results improve known complexity bounds by Deis et al. (IJAC 17 , 761–795 2007 ). Our results also apply to larger families of equations where no decidability has been previously known. The lower bound confirms a conjecture made in the conference version of this paper.

The idea behind this book is to provide the mathematical foundations for assessing modern developments in the Information Age. It deepens and complements the basic concepts, but it also considers instructive and more advanced topics. The treatise starts with a general chapter on algebraic structures; this part provides all the necessary knowledge for the rest of the book. The next chapter gives a concise overview of cryptography. Chapter 3 on number theoretic algorithms is important for developping cryptosystems, Chapter 4 presents the deterministic primality test of Agrawal, Kayal, and Saxena. The account to elliptic curves again focuses on cryptographic applications and algorithms. With combinatorics on words and automata theory, the reader is introduced to two areas of theoretical computer science where semigroups play a fundamental role.The last chapter is devoted to combinatorial group theory and its connections to automata. Contents:Algebraic structuresCryptographyNumber theoretic algorithmsPolynomial time primality testElliptic curvesCombinatorics on wordsAutomataDiscrete infinite groups

Traditionally, graph algorithms get a single graph as input, and then they should decide if this graph satisfies a certain property  Φ . What happens if this question is modified in a way that we get a possibly infinite family of graphs as an input, and the question is if there is a graph satisfying  Φ in the family? We approach this question by using formal languages for specifying families of graphs, in particular by regular sets of words. We show that certain graph properties can be decided by studying the syntactic monoid of the specification language  L if a certain torsion condition is satisfied. This condition holds trivially if L is regular. More specifically, we use a natural binary encoding of finite graphs over a binary alphabet Σ , and we define a regular set G ⊆ Σ ∗ such that every nonempty word w ∈ G defines a finite and nonempty graph. Also, graph properties can then be syntactically defined as languages over Σ . Then, we ask whether the automaton A specifies some graph satisfying a certain property  Φ . Our structural results show that we can answer this question for all “typical” graph properties. In order to show our results, we split L into a finite union of subsets and every subset of this union defines in a natural way a single finite graph F where some edges and vertices are marked. The marked graph in turn defines an infinite graph  F ∞ and therefore the family of finite subgraphs of F ∞ where F appears as an induced subgraph. This yields a geometric description of all graphs specified by  L based on splitting L into finitely many pieces; then using the notion of graph retraction, we obtain an easily understandable description of the graphs in each piece.

In 1965 Schützenberger published his famous result that star-free languages ( ) and aperiodic languages ( ) coincide over finite words, often written as . Perrin generalized to infinite words in the mid 1980s. In 1973 Schützenberger presented another (and less known) characterization of aperiodic languages in terms of rational expressions where the use of the star operation is restricted to prefix codes with bounded synchronization delay and no complementation is used. We denote this class of languages by . In this paper, we present a generalization of to infinite words. This became possible via a substantial simplification of the proof for the corresponding result for finite words. Moreover, we show that can be viewed as more fundamental than in the sense that the classical 1965 result of Schützenberger and its 1980s extension to infinite words by Perrin are immediate consequences of .

In a series of papers, Brzozowski together with Tamm, Davies, and Szykuła studied the quotient complexities of atoms of regular languages [6, 7, 3, 4]. The authors obtained precise bounds in terms of binomial sums for the most complex situations in the following five cases: (G): general, (R): right ideals, (L): left ideals, (T): two-sided ideals and (S): suffix-free languages. In each case let κc(n) be the maximal complexity of an atom of a regular language L, where L has complexity n ≥ 2 and belongs to the class C ϵ {G, R, L, T , S}. It is known that κT(n) ≤ κL(n) = κR(n) ≤ κG(n) < 3n and κS(n) = κL(n−1). We show that the ratio κC(n)/κC(n−1) tends exponentially fast to 3 in all five cases but it remains different from 3. This behaviour was suggested by experimental results of Brzozowski and Tamm; and the result for G was shown independently by Luke Schaeffer and the first author soon after the paper of Brzozowski and Tamm appeared in 2012. However, proofs for the asymptotic behavior of κG(n)/κG(n−1) were never published; and the results here are valid for all five classes above. Moreover, there is an interesting oscillation for all C: for almost all n we have κC(n)/κC(n−1) > 3 if and only if κC(n+1)/κC(n) < 3.

We give topological and algebraic characterizations as well as language theoretic descriptions of the following subclasses of first-order logic FO[<] for ω -languages: Σ 2 , FO 2 , FO 2 ∩Σ 2 , and Δ 2 (and by duality Π 2 and FO 2 ∩Π 2 ). These descriptions extend the respective results for finite words. In particular, we relate the above fragments to language classes of certain (unambiguous) polynomials. An immediate consequence is the decidability of the membership problem of these classes, but this was shown before by Wilke (Classifying Discrete Temporal Properties. Habilitationsschrift, Universität Kiel, April 1998 ) and Bojańczyk (Lecture Notes in Computer Science, vol. 4962, pp. 172–185, 2008 ) and is therefore not our main focus. The paper is about the interplay of algebraic, topological, and language theoretic properties.

QuickHeapsort is a combination of Quicksort and Heapsort. We show that the expected number of comparisons for QuickHeapsort is always better than for Quicksort if a usual median-of-constant strategy is used for choosing pivot elements. In order to obtain the result we present a new analysis for QuickHeapsort splitting it into the analysis of the partition-phases and the analysis of the heap-phases. This enables us to consider samples of non-constant size for the pivot selection and leads to better theoretical bounds for the algorithm. Furthermore, we introduce some modifications of QuickHeapsort. We show that for every input the expected number of comparisons is at most n log 2 n − 0.03 n + o ( n ) for the in-place variant. If we allow n extra bits, then we can lower the bound to n log 2 n − 0.997 n + o ( n ) . Thus, spending n extra bits we can save more that 0.96 n comparisons if n is large enough. Both estimates improve the previously known results. Moreover, our non-in-place variant does essentially use the same number of comparisons as index based Heapsort variants and Relaxed-Weak-Heapsort which use n log 2 n − 0.9 n + o ( n ) comparisons in the worst case. However, index based Heapsort variants and Relaxed-Weak-Heapsort require Θ ( n log n ) extra bits whereas we need n bits only. Our theoretical results are upper bounds and valid for every input. Our computer experiments show that the gap between our bounds and the actual values on random inputs is small. Moreover, the computer experiments establish QuickHeapsort as competitive with Quicksort in terms of running time.

In 1977, Makanin established the decidability of equations in free monoids. A key ingredient in his proof is the exponent of periodicity: for a word \\(w\\), it is the largest exponent \\(e\\) such that \\(w\\) contains a nonempty factor of the form \\(p^e\\). Makanin showed the following for a system of equations in free monoids: if the system has a solution with a sufficiently large exponent of periodicity, then it has infinitely many solutions. However, the converse -- whether the existence of infinitely many solutions implies the existence of solutions with arbitrarily large exponent of periodicity -- remains open. In this paper, we investigate the analogous problem for quadratic equations in finitely generated groups. We use normal forms to define the exponent of periodicity. We then identify structural conditions on groups and their normal forms that guarantee that infinite solution sets of quadratic systems have an unbounded exponent of periodicity. We prove that these conditions are preserved under graph products and, in particular, hold for all finitely generated right-angled Artin groups. In addition, we show that they also hold for finitely generated (graph products of) torsion-free nilpotent and hyperbolic groups, and we characterize the Baumslag-Solitar groups satisfying them.