A proof of Simon's theorem on piecewise testable languages

DOI10.1016/S0304-3975(96)00230-7zbMath0901.68093MaRDI QIDQ1391537

Peter M. Higgins

Publication date: 22 July 1998

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

testable languages

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items

Left and right negatively orderable semigroups and a one-sided version of Simon's theorem, Piecewise testable languages via combinatorics on words, Hierarchies of Piecewise Testable Languages, Tribute: The influence of Imre Simon's work in the theory of automata, languages and semigroups, REFLEXIVE RELATIONS, EXTENSIVE TRANSFORMATIONS AND PIECEWISE TESTABLE LANGUAGES OF A GIVEN HEIGHT, HIERARCHIES OF PIECEWISE TESTABLE LANGUAGES, The pseudovariety of semigroups of triangular matrices over a finite field, ORDERED AND $\mathcal{J}$-TRIVIAL SEMIGROUPS AS DIVISORS OF SEMIGROUPS OF LANGUAGES, Presentations for subsemigroups of $PD_n$

Cites Work

• Partially ordered finite monoids and a theorem of I. Simon
• On the semigroups of order-decreasing finite full transformations
• DIVISORS OF SEMIGROUPS OF ORDER-PRESERVING MAPPINGS ON A FINITE CHAIN
• Unnamed Item
• Unnamed Item
• Unnamed Item