Regular languages that are stutter-invariant but not star-free (LTL/FO-definable)

195 Views Asked by At

I am looking for simple examples and/or general ideas on regular languages (I am interested in finite words and infinite words alike) that are stutter-invariant (a language $L$ over an alphabet $A$ is stutterinvariant if the following holds: $uav \in L$ iff $uaav \in L$, where $u \in A^*, a\in A, v \in A^*$ respectively $v \in A^\omega$ in the infinite case) but not LTL-definable.

I am interested in such examples, because I have not quite understood the role of the Until-Operator in LTL and on which occassions one can have regular stutterinvariant-languages which are not definable just by using the Until-Operator.

A little background: The LTL-definable languages that are stutter-invariant are exactly the languages definable using only the Until-operator

Anyone some ideas/concepts/examples?

Kind regards

1

There are 1 best solutions below

0
On

$(a^+b^+a^+b^+)^*$ is stutter-invariant but is not LTL-definable since its syntactic monic is not aperiodic.