Convex and anti-convex languages

Abstract

We define here the counterpart of Jensen convex and anti-convex sets of real numbers for the case of languages. We investigate the existence of languages consisting only of strings in which a set of symbols is convex or anti-convex, as well as the place of such languages in Chomsky hierarchy. Local convexity is also briefly investigated.

Keywords:

• Jensen convexity
• convex and anti-convex languages
• Chomsky hierarchy
• operations with languages
• decidability

C.R. Categories:

• F.4.3
• G.2.1

^*Corresponding author

^*Corresponding author

Notes

^*Corresponding author

Additional information

Notes on contributors

Jürgen Dassow

a

Solomon Marcus

b