𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A proof of Simon's theorem on piecewise testable languages

✍ Scribed by Peter M. Higgins

Publisher
Elsevier Science
Year
1997
Tongue
English
Weight
587 KB
Volume
178
Category
Article
ISSN
0304-3975

No coin nor oath required. For personal study only.

✦ Synopsis

We give a new proof of the Theorem of I. Simon that a language is piecewise testable if and only if it is recognized by a finite F-trivial monoid. Our proof is based on representations by certain types of decreasing mappings.

πŸ“œ SIMILAR VOLUMES

A proof of choffrut's theorem on subsequ
A proof of choffrut's theorem on subsequential functions
✍ VΓ©ronique BruyΓ¨re; Christophe Reutenauer πŸ“‚ Article πŸ“… 1999 πŸ› Elsevier Science 🌐 English βš– 429 KB

We prove an extension of the Ginsburg-Rose theorem, and as a corollary, Choffrut's topological characterization of subsequential functions.

A quick proof of Seymour's theorem on t-
A quick proof of Seymour's theorem on t-joins
✍ AndrΓ‘s SebΓΆ πŸ“‚ Article πŸ“… 1987 πŸ› Elsevier Science 🌐 English βš– 163 KB

A very short proof of Seymour's theorem, stating that in bipartite graphs the minimum cardinality of a t-join is equal to the maximum cardinality of an edge-disjoint packing of t-cuts, is given. Let G be a graph and t:V(G)-, {0, 1}, where t(V(G)) is even. (If X~\_ V(G), then t(X):=E {t(x):xeX}.) A

A functional analysis proof of titchmars
A functional analysis proof of titchmarsh's theorem on convolution
✍ G.K. Kalisch πŸ“‚ Article πŸ“… 1962 πŸ› Elsevier Science 🌐 English βš– 306 KB

we mean as usual the space of complex-valued measurable functions defined on [0, 1] whose pth powers are integrable. By L~ [a, b] where 0 ~ a ~ b ~ 1 we shall mean here the closed subspace of L~[0, 1] consisting of functions vanishing a.e. on the complement of [a, b]. The support of a functionf defi