𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Squares of regular languages

✍ Scribed by Gerhard Lischke

Publisher
John Wiley and Sons
Year
2005
Tongue
English
Weight
127 KB
Volume
51
Category
Article
ISSN
0044-3050

No coin nor oath required. For personal study only.

✦ Synopsis

The square of a language L is the set of all words pp where p ∈ L. The square of a regular language may be regular too or context-free or none of both. We give characterizations for each of these cases and show that it is decidable whether a regular language has one of these properties.

πŸ“œ SIMILAR VOLUMES

Strongly Regular Square-free Graphs with
Strongly Regular Square-free Graphs with ΞΌ=2
✍ Benjamin V.C. Collins πŸ“‚ Article πŸ“… 1997 πŸ› Elsevier Science 🌐 English βš– 277 KB

By a square in an undirected graph ⌫ , we mean a cycle x , y , z , w such that x is not adjacent to z and y is not adjacent to w . Suppose that ⌫ is a strongly regular graph with ϭ 2 , and assume that ⌫ does not contain a square . Pick any vertex x of ⌫ and let ⌫ Ј denote the induced subgraph on the

Restorations of punctured languages and
Restorations of punctured languages and similarity of languages
✍ Gerhard Lischke πŸ“‚ Article πŸ“… 2006 πŸ› John Wiley and Sons 🌐 English βš– 165 KB

We investigate to which extent restoration of punctured languages is possible if the number of unknown positions or the proportion of unknown positions per word, respectively, is bounded, and we study their relationships for different boundings. The considered restoration classes coincide with simil

A block-preconditioner for a special reg
A block-preconditioner for a special regularized least-squares problem
✍ Tommy Elfving; Ingegerd Skoglund πŸ“‚ Article πŸ“… 2007 πŸ› John Wiley and Sons 🌐 English βš– 203 KB

## Abstract We consider a linear system of the form __A__~1~__x__~1~ + __A__~2~__x__~2~ + Ξ·=__b__~1~. The vector Ξ·consists of independent and identically distributed random variables all with mean zero. The unknowns are split into two groups __x__~1~ and __x__~2~. It is assumed that __A____A__~1~ h

Regular factors of regular graphs
Regular factors of regular graphs
✍ B. BollobΓ‘s; Akira Saito; N. C. Wormald πŸ“‚ Article πŸ“… 1985 πŸ› John Wiley and Sons 🌐 English βš– 242 KB

Given r 3 3 and 1 s A s r, we determine all values of k for which every r-regular graph with edge-connectivity A has a k-factor. Some of the earliest results in graph theory are due to Petersen [8] and concern factors in graphs. Among others, Petersen proved that a regular graph of even degree has a