# State-deterministic Finite Automata with Translucent Letters and Finite
Automata with Nondeterministically Translucent Letters

Benedek Nagy Department of Mathematics, Faculty of Arts and Sciences
Eastern Mediterranean University
99628 Famagusta, North Cyprus, Mersin-10, Turkey
and
Department of Computer Science, Institute of Mathematics and Informatics,
Eszterházy Károly Catholic University
Eger, Hungary<EMAIL_ADDRESS>
###### Abstract

Deterministic and nondeterministic finite automata with translucent letters
were introduced by Nagy and Otto more than a decade ago as Cooperative
Distributed systems of a kind of stateless restarting automata with window
size one. These finite state machines have a surprisingly large expressive
power: all commutative semi-linear languages and all rational trace languages
can be accepted by them including various not context-free languages. While
the nondeterministic variant defines a language class with nice closure
properties, the deterministic variant is weaker, however it contains all
regular languages, some non-regular context-free languages, as the Dyck
language, and also some languages that are not even context-free. In all those
models for each state, the letters of the alphabet could be in one of the
following categories: the automaton cannot see the letter (it is translucent),
there is a transition defined on the letter (maybe more than one transition in
nondeterministic case) or none of the above categories (the automaton gets
stuck by seeing this letter at the given state and this computation is not
accepting).

State-deterministic automata are recent models, where the next state of the
computation determined by the structure of the automata and it is independent
of the processed letters. In this paper our aim is twofold, on the one hand,
we investigate state-deterministic finite automata with translucent letters.
These automata are specially restricted deterministic finite automata with
translucent letters.

In the other novel model we present, it is allowed that for a state the set of
translucent letters and the set of letters for which transition is defined are
not disjoint. One can interpret this fact that the automaton has a
nondeterministic choice for each occurrence of such letters to see them (and
then erase and make the transition) or not to see that occurrence at that
time. Based on these semi-translucent letters, the expressive power of the
automata increases, i.e., in this way a proper generalization of the previous
models is obtained.

Keywords: finite state machines, automata with translucent letters,
determinism vs. nondeterminism, state-determinism

##  1 Introduction

The history of automata with translucent letters has begun using the technical
name cooperative distributed systems of stateless restarting automata with
window size one [28], while the term finite state acceptors with translucent
letters appeared in [17] reinterpreting the aforementioned technical name.
Basically (formal definitions will be recalled in Section 2), in a finite
automaton with translucent letters, in each state some of the letters of the
alphabet are translucent, and the automaton sees the first occurrence of a
non-translucent letter (after the occurrences of translucent letters in the
prefix of the remaining input in the given configuration, if any) and if there
is a transition defined on this letter (say, the letter is readable) in the
actual state, after erasing this letter, the next state is chosen according to
the transition function, and the computation continues. It may happen that
there are only translucent letters (or no letters at all) in the remained
input, then the computation is accepting if the actual state is a final state.
Automata with translucent letters can be applied in linguistics [27], and also
modelling various trace languages used to describe parallel processes [5, 11,
14, 26] based on commutations and partial commutations [3, 19].

In fact, there are various models in automata theory where the processing on
the input may not go strictly left to right. One of these models is the
restarting automata which is developed for linguistical motivation to do
analysis by reduction: in a nutshell, these automata have a read-write window
and they are searching for some specific pattern in the window to reduce,
i.e., shorten its content, and then they are restarting the computation on the
new content of the tape. It may also happen that the automaton accepts based
on what is in its window. Interested readers may be referred to [10, 37] to
see the various models, their computations, accepted languages and their
properties. Restarting R automata with window size one can do only one type of
reduction, to erase the letter in the window, hereby shortening the tape.
Stateless deterministic variants of them are the simplest models of restarting
automata. Instead of adding states to the system, their cooperative
distributed systems (shortly CD systems) are developed [28, 31] and found to
be very interesting with a surprisingly large expressive power as, e.g., they
are able to accept all rational trace languages. The components of such
systems play the role of the states in the reinterpreted model, in the
nondeterministic finite automata with translucent letter. Two types of
deterministic models of the CD systems of restarting R automata with window
size one are also studied [30]: In strictly deterministic models, the next
component is uniquely defined by the actual component and it does not depend
on the letter being processed (i.e., erased) in the actual computation step.
However, in globally deterministic CD systems of restarting R automata with
window size one the next component is deterministically chosen based on the
actual component and on the erased letter, somewhat similarly as it is in the
usual deterministic finite automata. Consequently, this letter model is
equivalent, by the reinterpretation, to the deterministic finite automata with
translucent letters.

Other models not consuming the input from left to right are various 2-head
models that process the input parallely from both extremes [7, 13, 18, 21, 22,
40]. Some of these finite state models are capable to accept exactly the
linear context-free languages. Moreover, in the bio-inspired models named
$5^{\prime}\to 3^{\prime}$ Watson-Crick finite automata, the automaton with
its both heads may read strings in a computation step [24, 35, 36]. There are
various interesting concepts related to determinism introduced and studied for
these $5^{\prime}\to 3^{\prime}$ Watson-Crick finite automata models. The
deterministic variant where the concept of determinism fits well to the usual
concept of determinism is less powerful in the sense that only a proper subset
of the class of the linear context-free languages can be accepted by them.
This class is called 2detLIN, and it is incomparable with the class detLIN
containing the languages that are accepted by deterministic one-turn pushdown
automata [34, 38]. The model where the next state is uniquely defined by the
actual state and does not depend on what is being processed from the input in
this step of computation is called state-deterministic and studied in [23]. At
$5^{\prime}\to 3^{\prime}$ Watson-Crick finite automata, the state-
deterministic variants are very restricted, but they may do some
nondeterministic computations, and thus, the language class accepted by them
is incomparable with 2detLIN. Other type of determinism, the quasi-determinism
is introduced and studied in [25]. In these automata, even if the state of the
next configuration is uniquely determined by the actual configuration (actual
state and remaining input), there could be more than one possible next
configuration. The quasi-deterministic $5^{\prime}\to 3^{\prime}$ Watson-Crick
finite automata accept a superclass of languages of both the classes accepted
by state-deterministic and by deterministic $5^{\prime}\to 3^{\prime}$ Watson-
Crick finite automata.

There are other models of computations which process the input not strictly
left to right, including various jumping automata [4, 15, 12] and input
revolving automata [2], just to mention a few more models. These models became
very popular in the last decades. The combination of the mentioned 2-head
finite state model with translucent letters allow to accept all linear trace
languages [33]. Pushdown automata with translucent letters can be used to
characterise context-free trace languages [29].

In this paper, on the one hand, we investigate the state-deterministic finite
automata with translucent letters and give some results on the class of
languages accepted by them.

On the other hand, we investigate finite automata with translucent letters by
relaxing the condition that for a state the set of translucent and readable
letters is disjoint. In this way, the translucency becomes nondeterministic
and thus, we may expand both the deterministic and nondeterministic finite
automata with translucent letters to allow nondeterministic translucency. Our
other main result is that we can show that this model is a real expansion of
the basic models, the class of accepted languages is a superclass of the class
languages of the original model.

Recently another extension of the finite automata with translucent letters was
investigated in which in the computation the head is not restarting after
erasing a symbol, but continues from the position where this letter has been
erased [16]. We believe that our new type of restrictions and extensions are
also giving some new interesting insights and results to this particular field
of automata theory.

The structure of the paper is as follows. In the next section we recall some
formal preliminaries and the basic definitions of finite automata with
translucent letters. Section 3 is devoted to a restricted class of
deterministic models, namely, to the state-deterministic finite automata with
translucent letters; while in Section 4 we present our other new concept by
allowing nondeterminism based on translucency. We show that this model is more
powerful than the original model, however, still only semi-linear languages
can be accepted. Finally, conclusions close the paper.

##  2 Preliminaries

We assume that the reader is familiar with the basic concepts of formal
languages and automata [8, 9], however, to fix our notations, we formally
recall some basic definitions. We denote the empty word by $\lambda$.

We say that the languages $L_{1}$ and $L_{2}$ are letter equivalent, if for
any word $x\in L_{1}$ we may find a word $y\in L_{2}$ such that $y$ is
obtained from $x$ by reordering (permuting) its letters and also for any word
$x\in L_{2}$ we may find a word $y\in L_{1}$ with the same property. It is
known that a language is _semi-linear_ if there is a regular language that is
letter equivalent with it. All context-free languages are semi-linear [39] and
there are context-sensitive languages that are not semi-linear. We do not
detail here partial commutations, commutations, traces and trace languages,
interested readers may be referred to [3, 5] and for their relations to
automata with translucent letters to [28, 29, 33].

A _nondeterministic finite automaton_ (NFA) is a pentuple
$A=(Q,\Sigma,I,F,\delta)$, where $Q$ is the finite set of internal states,
$\Sigma$ is the finite alphabet containing the input letters, $I\subseteq Q$
is the set of initial states, $F\subseteq Q$ is the set of final (or
accepting) states, and $\delta:Q\times\Sigma\to 2^{Q}$ is the transition
relation. If $|I|=1$ and $|\delta(q,a)|\leq 1$ holds for all $q\in Q$ and all
$a\in\Sigma$, then $A$ is a _deterministic finite automaton_ (DFA). Notice
that, in general, in NFAs we allow multiple initial states, but we do not
allow transitions by the empty word.

An NFA $A$ works as follows. Let an input string $w\in\Sigma^{*}$ be given,
then $A$ starts its computation in a state $q_{0}$ that is chosen
nondeterministically from the set $I$ of all initial states. This
configuration is encoded as $q_{0}w$ (for simplicity, we may assume that
$Q\cap\Sigma=\emptyset$). Now $A$ reads the first letter of $w$, say $a$ (let
$w=au$), thereby deleting (consuming) this occurrence of letter $a$, and it
changes its internal state to a state $q_{1}$ that is chosen
nondeterministically from the set $\delta(q_{0},a)$, formally we may write
that the new configuration $q_{1}u$ is reached. However, it may happen that
$\delta(q_{0},a)$ is empty, then $A$ gets stuck and this computation fails in
this input. Otherwise, $A$ continues the computation from the configuration
$q_{1}u$ by reading the input letter by letter until either $w$ has been
consumed completely or the computation fails (similarly as we have described).
We say that $A$ accepts $w$ from the initial configuration $q_{0}w$ if it
reaches a configuration $q_{f}\cdot\lambda$ in a computation starting from
$q_{0}w$, where $q_{f}\in F$ is a final state. By $L(A)$ we denote the set of
all strings $w\in\Sigma^{*}$ for which $A$ has an accepting computation in the
sense described above.

It is well-known that the class of languages that are accepted by NFAs
coincides with the class of regular languages, and that DFAs accept exactly
the same languages.

Now we recall the nondeterministic finite automata with translucent letters
from [17].

A _finite state automaton with translucent letters_ (NFAwtl) is defined as
$A=(Q,\Sigma,\$,\tau,I,F,\delta)$, where $Q$, $\Sigma$, $I$ and $F$ are the
same as at an NFA; $\$\not\in\Sigma$ is a special symbol that is used
technically as an _endmarker_ , $\tau:Q\to 2^{\Sigma}$ is the _translucency
mapping_ , and $\delta:Q\times\Sigma\to 2^{Q}$ is the _transition relation_
that satisfies the following condition:

$\forall q\in Q\;\forall a\in\tau(q):\delta(q,a)=\emptyset.$

For each state $q\in Q$, the letters from the set $\tau(q)$ are translucent
for $q$, that is, in state $q$ the automaton $A$ does not see these letters.
$A$ is called _deterministic finite state automaton with translucent letters_
, abbreviated as DFAwtl, if $|I|=1$ and if $|\delta(q,a)|\leq 1$ for all $q\in
Q$ and all $a\in\Sigma$.

An NFAwtl $A=(Q,\Sigma,\$,\tau,I,F,\delta)$ works as follows. Let
$w\in\Sigma^{*}$ be an input word. $A$ starts in a nondeterministically chosen
initial state $q\in I$ with the word $w\cdot\$$ on its input tape, that is
$q_{0}w\$$ is an initial configuration. A computation step of $A$ is defined
as follows. Assume that $w=a_{1}a_{2}\cdots a_{n}$ for some $n\geq 1$ and
$a_{1},\ldots,a_{n}\in\Sigma$. Then $A$ looks for the first occurrence from
the left of a letter that is not translucent (say visible) for the current
state $q$, more precisely, if $w=uav$ such that $u\in(\tau(q))^{*}$ and
$a\not\in\tau(q)$, then $A$ nondeterministically chooses a state
$q^{\prime}\in\delta(q,a)$, erases the letter $a$ from the tape thus producing
the tape contents $uv\cdot\$$, and its internal state is set to $q^{\prime}$.
Therefore after this computation step the configuration is $q^{\prime}uv\$$
and the computation continues from this configuration by looking for the first
visible letter of $uv$ at state $q^{\prime}$. However, it may happen that
$\delta(q,a)=\emptyset$ for the first visible letter $a$, $A$ halts without
accepting, this computation fails. Finally, if $w\in(\tau(q))^{*}$ for a
configuration $qw\$$ (including the possibility that the configuration is in
fact $q\cdot\lambda\cdot\$$), then $A$ reaches the $-symbol and the
computation halts. In this case $A$ accepts if $q\in F$ is a final state;
otherwise, it does not accept. A word $w\in\Sigma^{*}$ is _accepted by_ $A$ if
there exists an initial state $q_{0}\in I$ and an accepting computation from
$q_{0}w\cdot\$$. Further, the empty word $\lambda$ is accepted by $A$ if there
exists an initial state $q_{0}\in Q$ such that $q_{0}$ is also a final state.
Now $L(A)=\\{\,w\in\Sigma^{*}\mid w\mbox{ is accepted by }A\,\\}$ is the
_language accepted by_ $A$. Notice that the endmarker is, in fact, needless;
we kept it only for traditional reason.

The classical _nondeterministic finite automata_ (NFA) is obtained from the
NFAwtl by removing the endmarker $\$$ and by ignoring the translucency
relation $\tau$, and the _deterministic finite-state acceptor_ (DFA) is
obtained from the DFAwtl in the same way. Thus, the NFA (DFA) can be
interpreted as a special type of NFAwtl (DFAwtl). Accordingly, all regular
languages are accepted by DFAwtl. Moreover, DFAwtls are much more expressive
than standard DFAs as shown by the following example.

###### Example 1

Consider the DFAwtl $A=(Q,\Sigma,\$,\tau,I,F,\delta)$, where
$Q=\\{q_{0},q,q_{a},q_{b},q_{c},q_{d}\\}$, $I=\\{q_{0}\\}$, $F=\\{q\\}$,
$\Sigma=\\{a,b,c,d\\}$, and the functions $\tau$ and $\delta$ are defined as
follows:

$\begin{array}[]{rclrcl}\tau(q_{0})&=&\\{b,c,d\\},&\delta(q_{0},a)&=&\\{q_{a}\\},\\\
\tau(q)&=&\emptyset,&\delta(q,a)&=&\\{q_{a}\\},\ \delta(q,b)=\\{q_{b}\\},\
\delta(q,c)=\\{q_{c}\\},\ \delta(q,d)=\\{q_{d}\\},\\\
\tau(q_{a})&=&\\{a,c,d\\},&\delta(q_{a},b)&=&\\{q\\},\\\
\tau(q_{b})&=&\\{b,c,d\\},&\delta(q_{b},a)&=&\\{q\\},\\\
\tau(q_{c})&=&\\{a,b,c\\},&\delta(q_{c},d)&=&\\{q\\},\\\
\tau(q_{d})&=&\\{a,b,d\\},&\delta(q_{d},c)&=&\\{q\\}.\end{array}$

Further, $\delta(p,x)=\emptyset$ for all other pairs $(p,x)\in Q\times\Sigma$.
Firstly, the input must have an $a$, which is consumed in the first step of
the computation, then a $b$ is consumed. One may see that after that the
automaton reads the first letter of the remaining input and depending on what
it was, in the next step consumes the first occurrence of a letter that is a
pair of the previously erased one, where pairs are $a$-s with $b$-s and $c$-s
with $d$-s. Consequently $A$ accepts the language
$L^{ab}=\\{w\in\\{a,b,c,d\\}^{*}~{}|~{}|w|_{a}=|w|_{b}>0\text{ and
}|w|_{c}=|w|_{d}\\}$. Similarly, by permuting the roles of the letters, e.g.,
the language $L^{ac}=\\{w\in\\{a,b,c,d\\}^{*}~{}|~{}|w|_{a}=|w|_{c}>0\text{
and }|w|_{b}=|w|_{d}\\}$ is also accepted by a DFAwtl. However, the union of
these two languages can be accepted by an NFAwtl, but cannot with any DFAwtl.
This latter fact can be shown somewhat analogously to the fact that the
context-free language
$\\{a^{n}b^{n}c^{m}d^{m}\\}\cup\\{a^{n}b^{m}c^{m}d^{n}\\}$ is not
deterministic context-free. We skip the formal proof because the lack of
space.

As we have already described NFAwtl and DFAwtl are reformulations of
cooperative distributed systems of stateless deterministic restarting R
automata with window size one. The DFAwtl, in fact, are reinterpretations of
stateless globally deterministic CD-R(1)-systems [30].

Recently various concepts about deterministic computations have been emerged,
therefore, we recall the concept of state-determinism from [23].

An automaton is _state-deterministic_ if for each of its state $q\in Q$, if
there is a transition from $q$ and it goes to state $p$ (i.e.,
$p\in\delta(q,a)$), then every transition from $q$ goes to $p$, that is, if an
automaton has state $q$ in its actual configuration, then, if the computation
continues, the state of the next configuration is uniquely determined and it
is $p$.

We are continuing the paper in this line.

##  3 On state-deterministic finite automata with translucent letters

As our first result, we investigate the state-deterministic FAwtl (SFAwtl for
short) by applying this type of concept of determinism to NFAwtl.

First, we recall the concept of _stateless strictly deterministic
CD-R(1)-systems_ [30]. In these systems there is only one initial state, and
there is exactly one successor component for each component. One may think,
that in the terminology of finite automata with translucent letters we can
interpret it with the conditions $|I|=1$ and for each $q\in Q$,
$\left|\bigcup_{a\in\Sigma}\delta(q,a)\right|=1$ which may lead to a very
similar concept as state-determinism. However, this is not exactly the case,
stateless strictly deterministic CD-R(1)-systems and the state-deterministic
FAwtl are in close relation, but in a CD-R(1)-system one may use the
computation step “Accept” at any component on a given non translucent letter,
while in NFAwtl the acceptance condition is defined in a different way. We are
showing some explicit difference of these models in this section.

We present an example to show that these restricted automata are still able to
accept non trivial languages.

###### Example 2

Let $A=(Q,\Sigma,\$,\tau,I,F,\delta)$, where $Q=\\{q_{0},q_{1}\\}$,
$I=\\{q_{0}\\}=F$, $\Sigma=\\{0,1\\}$, and the functions $\tau$ and $\delta$
are defined as follows:

$\begin{array}[]{rclrcl}\tau(q_{0})&=&\emptyset,&\delta(q_{0},0)&=&\\{q_{1}\\},\\\
\tau(q_{1})&=&\\{0\\},&\delta(q_{1},1)&=&\\{q_{0}\\}.\end{array}$

By observing the structure of this automaton, it is clearly state-
deterministic. Considering the accepted language, it is the Dyck language,
where $0$ refers to opening and $1$ to closing brackets.

###### Example 3

Let $A=(Q,\Sigma,\$,\tau,I,F,\delta)$, where
$Q=\\{q_{0},q_{1},q_{2},q_{3}\\}$, $I=\\{q_{0}\\}=F$, $\Sigma=\\{a,b,c,d\\}$,
and the functions $\tau$ and $\delta$ are defined as follows:

$\begin{array}[]{rclrcl}\tau(q_{0})&=&\emptyset,&\delta(q_{0},a)&=&\\{q_{1}\\},\\\
\tau(q_{1})&=&\\{a,c,d\\},&\delta(q_{1},b)&=&\\{q_{2}\\},\\\
\tau(q_{2})&=&\\{a,b,d\\},&\delta(q_{2},c)&=&\\{q_{3}\\},\\\
\tau(q_{3})&=&\\{a,b,c\\},&\delta(q_{3},d)&=&\\{q_{0}\\}.\end{array}$

Further, $\delta(q,x)=\emptyset$ for all other pairs $(q,x)\in Q\times\Sigma$.
On the one hand, it is easy to check that $A$ is a DFAwtl which is, in fact,
also state-deterministic. On the other hand, the language accepted by $A$
intersected by the regular language $a^{*}d^{*}c^{*}b^{*}$ is the non context-
free language $\\{a^{n}d^{n}c^{n}b^{n}~{}|~{}n\geq 0\\}$, and thus $A$ accepts
a language that is not context-free.

From this example, using the fact that any language accepted by NFAwtl has a
letter-equivalent sublanguage that is regular [28] (but the language
$\\{a^{n}d^{n}c^{n}b^{n}~{}|~{}n\geq 0\\}$ does not), we can deduce that:

###### Proposition 1

The language class accepted by state-deterministic FAwtl is not closed under
intersection with regular languages.

Based on [23], we know that state-deterministic FAwtl have the graph structure
with no branching, that is, either a line graph (starting from the sole
initial state) or a line graph with an additional edge from the last state to
a state.

Clearly languages like $a^{*}$, $b^{*}$, $a+aaa$, $ab+ba$ are accepted by
state-deterministic FAwtl with 1, 1, 4 and 3 states, respectively. For $ab+ba$
translucency can be used in the initial state, e.g., $a$ is translucent and
transition with $b$ leads to the next state, from which the computation may
continue by reading an $a$ to reach the final state.

Now, we present a relatively simple example language that is not accepted by
any SFAwtl.

###### Example 4

The regular language described by $a^{*}+b^{*}$ is not accepted by any state-
deterministic FAwtl. It is easy to see that, by assuming that an SFAwtl $A$
accepts the given language, after reading an $a$ or a $b$, $A$ must be in the
same state, however, the possible computations after erasing an $a$ or erasing
a $b$ must not be the same, since this would lead to accept words containing
both $a$ and $b$, contradicting to our assumption on the accepted language.

Based on the above example, we may deduce the following closure property:

###### Proposition 2

The language class accepted by SFAwtl is not closed under union.

We may also summarize some hierarchy type results based on the previously
shown examples.

###### Proposition 3

State-deterministic FAwtl are deterministic, i.e., they are also DFAwtl.
Further, the language class accepted by SFAwtl includes some non context-free
languages, but on the other hand, does not include all regular languages.

We recall from [32] that the language class accepted by stateless strictly
deterministic CD-R(1)-systems is closed under complement. We show that this is
not the case with the state-deterministic FAwtl, thus, in this way, we also
show that the new concept is not a reinterpretation of these CD systems.

###### Proposition 4

The language class accepted by SFAwtl is not closed under complement.

######  Proof 3.1.

On the one hand, as we have described, the Dyck language over $\\{0,1\\}$ is
accepted by state-deterministic FAwtl. Now, on the other hand, we show that
its complement $L^{c}$ is not. Let as assume towards a contradiction that
there is an SFAwtl $A$ that accepts $L^{c}$. Since $\lambda$ is not in
$L^{c}$, the initial state $q_{0}$ is not a final state of $A$. Let us
consider the cases by seeing which of the letters could be translucent at
$q_{0}$.

  * •

Clearly, it cannot happen that both $0$ and $1$ are translucent, since then,
no words would be accepted.

  * •

In case either $0$ or $1$ is translucent, there must be a transition with the
other letter from $q_{0}$, to another state, say state $q_{1}$. Now, on the
one hand, the input $01$ should not be accepted, but the input $10$ should be.
However, in this case, both of these inputs lead to the same configuration
after the first step of the computation. This leads to a contradiction, since
from here either both of them are accepted by $A$, or none of them.

  * •

The last possibility is when there are no translucent letters at $q_{0}$.
Since $A$ must accept words starting with $0$, e.g., $0,00,000,001,010$ and
also words starting with $1$, e.g., $1,10,11,100$, the transition with both
$0$ and $1$ must go an accepting state $q_{1}$, i.e.,
$\delta(q_{0},a)=\delta(q_{0},b)=q_{1}$. Considering the possible input words
$01$ and $11$, thus we reach the same configuration $q_{1}1\$$, however, the
former word should not be accepted, while the latter one is in $L^{c}$. By
this contradiction, the proof has been finished.

######  Proposition 3.2.

The language class accepted by SFAwtl is not closed under concatenation.

######  Proof 3.3.

Let us consider the languages $a+aaa$ and $b$ which both are accepted by
state-deterministic FAwtl. Let us consider now their concatenation
$L_{c}=\\{ab,aaab\\}$. Let us assume that there is an SFAwtl $A$ that accepts
$L_{c}$. In its initial state $q_{0}$, there are the following options:

  * •

There is no translucent letters for $q_{0}$, then there must be a transition
with $a$ to a state $q_{1}(\neq q_{0})$ and no other transition from $q_{0}$.
Neither $q_{0}$, nor $q_{1}$ is a final state. Now, at $q_{1}$ $A$ should be
able to read a $b$ and it must reach an accepting state $q_{2}$. Now there are
two subcases:

    * –

If there is no translucency used at $q_{1}$, it must also have a transition
with $a$ (to $q_{2}$) allowing to process the word $aaab$, however, in this
case there would be a false acceptance of $aa$ by $A$ arriving to a
contradiction.

    * –

In the second subcase, $a$ must be translucent in $q_{1}$, and thus from the
original input $aaab$, the remaining was $aab$ and in this way the last letter
$b$ could be read, and then the remaining $aa$ should be accepted. However, in
this case $A$ would also accept the word $abaa$ with a similar computation as
$aaab$ contradicting to the fact that it accepts $L_{c}$.

  * •

If $a$ is translucent at $q_{0}$, then we must have a transition with $b$,
then from $q_{1}$ $A$ should able to accept the remaining word $a$. However,
in this case a similar computation would accept also $ba$ as the computation
for $ab$. Contradiction.

  * •

If $b$ is translucent at $q_{0}$, then we must have a transition with $a$,
leading to the state $q_{1}$, similarly as in the first case. For $q_{1}$ the
proof works in exactly in the same way as in that case.

  * •

If both $a$ and $b$ are translucent in $q_{0}$, no transition can be defined,
consequently, the nonempty language $L_{c}$ cannot be accepted in this way.

##  4 The new models with nondeterministic translucency

In this section, first we provide the formal definition of the new automata
models and their work.

A _(deterministic) finite state automaton with nondeterministically
translucent letters_ , abbreviated as (DFAwntl) NFAwntl, is defined as a
septuple $A=(Q,\Sigma,\$,\tau,I,F,\delta)$, similarly to NFAwtl (DFAwtl),
respectively, but without the condition that $\forall q\in Q\;\forall
a\in\tau(q):\delta(q,a)=\emptyset.$ That is, for an NFAwntl (DFAwntl) it is
allowed that for a state $q\in Q$ and for a letter $a\in\Sigma$ both
$a\in\tau(q)$ and $\delta(q,a)\neq\emptyset$ hold. Notice that at a DFAwntl,
there is only one initial state, and there is at most one transition defined
for any input letter, as at DFAwtl.

A computation step of $A$ is defined as follows. Assume that
$w=a_{1}a_{2}\cdots a_{n}$ for some $n\geq 1$ and
$a_{1},\ldots,a_{n}\in\Sigma$ and $A$ is in state $q$. Then $A$ looks for an
occurrence of a letter (say $a_{i}=b$) for which a transition is defined,
i.e., $\delta(q,b)\neq\emptyset$ such that each letter $a_{j}\in\tau(q)$ with
$j<i$. In this way, the actual configuration can be written as $q\cdot ubv\$$
with letter $b$ in the position of $a_{i}$, $u\in\tau(q)^{*}$,
$v\in\Sigma^{*}$, and the next configuration could be $p\cdot uv\$$ for a
state $p\in\delta(q,b)$.
On the other hand, it may happen that such letter $a_{i}$ does not exist,
i.e., there is a letter $a_{i}=c\not\in\tau(q)$ such that for each $j<i$
$a_{j}\in\tau(q)$ and $\delta(q,a_{k})=\emptyset$ (for all $k\leq j$)
including $\delta(q,c)=\emptyset$. In this case $A$ halts without accepting;
this computation fails.
Further, if $w\in(\tau(q))^{*}$ for a configuration $qw\$$ with $q\in F$, then
$A$ reaches the $-symbol and the computation halts by accepting.
Finally, $w\in(\tau(q))^{*}$, $q\not\in F$ and there is no letter in $w$ for
which a transition has been defined ($\delta(q,a_{i})=\emptyset$ for each $i$,
or $w=\lambda$), then the computation fails: $A$ does not accept.

A word $w\in\Sigma^{*}$ is _accepted by_ $A$ if there exists an initial state
$q_{0}\in I$ and an accepting computation from $q_{0}w\cdot\$$. Now
$L(A)=\\{\,w\in\Sigma^{*}\mid w\mbox{ is accepted by }A\,\\}$ is the _language
accepted by_ $A$.

Based on these definitions, we can define four categories of NFAwtl:

translucency $\backslash$ transition mapping | deterministic | nondeterministic
---|---|---
disjoint | DFAwtl | NFAwtl
nondeterministic | DFAwntl | NFAwntl

As we will show although the model DFAwntl seems deterministic by its
transition function, we may easily cheat by the nondeterminism allowed by
translucency.

######  Example 4.4.

Let $A=(Q,\Sigma,\$,\tau,I,F,\delta)$, where
$Q=\\{q_{0},q_{a},q_{b},q_{c}\\}$, $I=\\{q_{0}\\}$, $F=\\{q_{c}\\}$,
$\Sigma=\\{a,b,c\\}$, and the functions $\tau$ and $\delta$ are defined as
follows:

$\begin{array}[]{rclrcl}\tau(q_{0})&=&\emptyset,&\delta(q_{0},a)&=&\\{q_{a}\\},\delta(q_{0},b)=\\{q_{b}\\},\delta(q_{0},c)=\\{q_{c}\\},\\\
\tau(q_{a})&=&\\{a,b,c\\},&\delta(q_{a},b)&=&\\{q_{0}\\},\\\
\tau(q_{b})&=&\\{a,b,c\\},&\delta(q_{b},a)&=&\\{q_{0}\\},\\\
\tau(q_{c})&=&\emptyset.&\end{array}$

Further, $\delta(q,x)=\emptyset$ for all other pairs $(q,x)\in Q\times\Sigma$.
It is easy to check that $A$ is a DFAwntl.
Let us see how $A$ works. Since there are no translucent letters in $q_{0}$,
$A$ consumes the first letter of the remaining input always in this state. If
it was an $a$, then it erases a $b$ from anywhere in the tape; if $A$ consumes
a $b$ at state $q_{0}$, then in the next computation step $A$ erases an $a$
from anywhere in the tape. Finally, the input is accepted if only a $c$
remains on the tape and $A$ is in state $q_{0}$, then it reaches the accepting
state $q_{c}$.

Thus, for every accepted word the number of its $a$-s and $b$-s are the same
and it contains a $c$. Let us write such a word in the form $vcu$ with
$v,u\in\\{a,b\\}^{*}$. It is also easy to see that $A$ may accept various
words where $|v|\geq|u|$, but no words with $|v|<|u|$. On the other hand, let
us see which words are accepted with the property $|v|=|u|$. By the work of
$A$, the conditions $|v|_{a}=|u|_{b}$ and $|v|_{b}=|u|_{a}$ must hold, i.e.,
in $v$ the number of $a$-s is the same as the number of $b$-s in $u$ and vice
versa.

Now we are arguing that the same language cannot be accepted by any NFAwtl
without using nondeterministic translucency (due to lack of space we skip some
parts of the formal proof). Let us assume that there is an NFAwtl $B$ that
accepts the same language as $A$. Let the number of states of $B$ is $n$. Let
us consider a word $w=a^{k}b^{\ell}ca^{\ell}b^{k}\in L(A)$ with $k,\ell>2n$.
By our assumption $B$ accepts $w$, thus consider an accepting computation on
$w$ by $B$. Clearly, there are two cases based on the first $n+1$ steps of the
computation.

  * •

If letter $c$ is erased during these computation step, then it can be shown
that some words $vcu$ with $|v|<|u|$ would also be accepted by $B$ having all
the letters processed after the step in which $c$ is read after the $c$ in the
original input word.

  * •

If $c$ is not read during the first $n+1$ steps, only $a$-s and $b$-s before
the $c$ (in part $v$) are accessed and processed in the first $n+1$ steps.
However, by the pigeon-hole principle, a state is repeated during these steps,
meaning that there are also values $i$ and $j$ ($0\leq i,j\leq n+1$, $i+j>0$)
such that from input $w^{\prime}=a^{k-i}b^{\ell-j}ca^{\ell}b^{k}$ in $n+1-i-j$
steps exactly the same configuration is reached as from $w$ in $n+1$ steps. In
this case, by continuing the computation on $w^{\prime}$ in the same way as
the accepting computation on $w$, the word $w^{\prime}$ will also be accepted.

Now, in both cases, we have reached contradiction by accepting words of the
form $vcu$ for which $|v|<|u|$.

###  4.1 Hierarchy of the accepted languages

In this subsection our aim is to give some hierarchy like results by
establishing where the new families of languages are comparing them to various
other classes.

First, we note that, in fact, the following inclusions hold by definition.

######  Proposition 4.5.

Every NFAwtl is an NFAwntl and every DFAwtl is a DFAwntl.
Moreover, every DFAwntl is an NFAwntl.

Based on Example 4.4, we can also state some hierarchy results on the accepted
language classes.

######  Proposition 4.6.

The language class accepted by NFAwtl is a proper subclass of the language
class accepted by NFAwntl.
The language class accepted by DFAwtl is a proper subclass of the language
class accepted by DFAwntl.

Here, we leave open the question if NFAwntl is more efficient and expressive
than DFAwntl.

On the one hand, we have seen that we can construct DFAwntl that accept some
non context-free languages. Now, on the other hand, let us show some of their
limitations.

To compare the new language classes with some classical classes of formal
languages we establish the following result.

######  Lemma 4.7.

For every language accepted by an NFAwntl (DFAwntl), there is a letter
equivalent sublanguage that is accepted by an NFAwtl (DFAwtl, resp.).

######  Proof 4.8.

In case there is no such letter in any state which is both in the set of
translucent letters and there is also a transition on it, the automaton is in
fact, an NFAwtl (also a DFAwtl in deterministic case) and its language, as its
own sublanguage, fulfils the statement of the lemma.

Now, let us assume that automaton $A$ is an NFAwntl, but it is not an NFAwtl.
On the one hand, since there is no “forced” way not to see a letter for which
a transition is defined, $A$ may always consumes the first occurrence of such
a letter and in fact accepts words of a language that is also accepted by an
NFAwtl. More precisely, by removing those letters from the translucency set of
a state for which transitions are defined, an NFAwtl (DFAwtl) $A^{\prime}$ can
be obtained. Clearly all words that $A^{\prime}$ may accept are also accepted
by $A$ with a similar computation.

To see that this language is letter equivalent to the originally accepted
language, consider a computation on any of the accepted word by $A$. Since the
automaton never knows if the consumed letter in a computation step is the
first or only reached through some translucent letters, we may reorder the
input according to an accepting computation, and in this way for each accepted
word there will be a letter equivalent word that has also been accepted by
$A^{\prime}$.

Moreover, if, by chance, the letters of the input are ordered in exactly the
way as they are consumed during an accepting computation, then, in fact, an
NFAwntl is working in the same way as an NFA, thus we may also establish the
following fact:

######  Lemma 4.9.

For every language accepted by an NFAwntl, there is a letter equivalent
regular sublanguage.

From the previous lemma we can conclude:

######  Corollary 4.10.

All languages accepted by NFAwntl are semi-linear.

This could be interesting in the mirror of the fact, that by changing the
window size of an R automata from 1 to 2 (like allowing to have the
translucency and transitions not letter by letter, but somehow by pairs of
consecutive letters), the corresponding model, the CD system of stateless
deterministic R(2) automata is able to accept some non semi-linear languages
[20].

On the other hand, as the linear context-free language $\\{a^{n}b^{n}\\}$ does
not have any letter equivalent regular sublanguage, there is no NFAwntl that
could accept it. Since $\\{a^{n}b^{n}\\}$ is deterministic linear and also in
2detLIN (accepted by deterministic 2-head finite automata consuming the input
letters from the two extremes until they are meeting [34]), we have the
following incomparability results.

######  Theorem 4.11.

The language classes accepted by NFAwntl and DFAwntl properly include the
class of regular languages. Further, the language classes accepted by NFAwntl
and DFAwntl are incomparable to each of the following classes of languages:
deterministic linear, 2detLIN, linear context-free, deterministic context-
free, context-free.

Finally, we analyse the computations of DFAwntl.

###  4.2 Simulating nondeterministic computations with DFAwntl

In this section our aim is to show that although seemingly by the transition
function, DFAwntl seem to be deterministic automata, they have some real
nondeterministic features.

######  Example 4.12.

As we mentioned in Example 1, there are DFAwtl that accept the languages

$L^{ab}=\\{w\in\\{a,b,c,d\\}^{*}~{}|~{}|w|_{a}=|w|_{b}>0\text{ and
}|w|_{c}=|w|_{d}\\},$
$L^{ac}=\\{w\in\\{a,b,c,d\\}^{*}~{}|~{}|w|_{a}=|w|_{c}>0\text{ and
}|w|_{b}=|w|_{d}\\}$

and

$L^{ad}=\\{w\in\\{a,b,c,d\\}^{*}~{}|~{}|w|_{a}=|w|_{d}>0\text{ and
}|w|_{b}=|w|_{c}\\}.$

Let these automata be having the set of states
$Q^{ab}=\\{q_{0}^{ab},q_{a}^{ab},q_{b}^{ab},q_{c}^{ab},q_{d}^{ab},q^{ab}\\}$;
$Q^{ac}=\\{q_{0}^{ac},q_{a}^{ac},q_{b}^{ac},q_{c}^{ac},\\\
q_{d}^{ac},q^{ac}\\}$ and
$Q^{ad}=\\{q_{0}^{ad},q_{a}^{ad},q_{b}^{ad},q_{c}^{ad},q_{d}^{ad},q^{ad}\\}$,
respectively.

The union of these languages cannot be accepted by any DFAwtl. Let us define
now a DFAwntl as follows.

$A=(Q,\Sigma,\$,\tau,I,F,\delta)$, where $Q=Q^{ab}\cup Q^{ac}\cup
Q^{ad}\cup\\{q_{0}\\}$, $I=\\{q_{0}\\}$, $F=\\{q^{ab},q^{ac},q^{ad}\\}$,
$\Sigma=\\{a,b,c,\\\ d\\}$, and the functions $\tau$ and $\delta$ are defined
as follows:

$\tau(q_{0})=\\{a,b,c,d\\},\hskip
42.67912pt\delta(q_{0},a)=\emptyset,\delta(q_{0},b)=\\{q_{b}^{ab}\\},\delta(q_{0},c)=\\{q_{c}^{ac}\\},\delta(q_{0},d)=\\{q_{d}^{ad}\\}$

for the newly added initial state and they are inherited from the respective
automata for each other state.

Now, for any input, $A$ nondeterministically guesses in which of the three
languages the input is: as $\tau(q_{0})=\Sigma$ it has access to any
occurrence of a $b$, a $c$ or a $d$ as transitions are defined for these
letters in $q_{0}$. By guessing the input belonging to $L^{ab}$, it should
have at least one $b$, thus by reading a $b$ in the first step, the
subautomaton accepting $L^{ab}$ is chosen such that a $b$ has already been
processed. Now, it is easy to see that after this nondeterministic choice in
the first step, the computation continues in a deterministic manner. The other
nondeterministic choices in the first step of the computation are: by
consuming a $c$ anywhere from the input $A$ chooses to check whether the input
belongs to $L^{ac}$, and by consuming a $d$ anywhere from the input in the
first step of the computation, $A$ chooses to check whether the input belongs
to $L^{ad}$. If the guess was correct, the input will be accepted. Otherwise,
$A$ must use another computation to accept the given input, if any.
Consequently the DFAwntl $A$ accepts $L^{ab}\cup L^{ac}\cup L^{ad}$.

We left open if NFAwntl can accept more languages than DFAwntl (the properness
of the inclusion relation of these two language classes is open). It is known
(see [32], for the proof) that DFAwtl cannot accept all rational trace
languages, and this fact was used to prove the properness of the hierarchy
between NFAwtl and DFAwtl. Actually, it was shown that the language
$\\{w\in\\{a,b\\}^{*}~{}|~{}|w|_{a}=|w|_{b}\text{ or }2|w|_{a}=|w|_{b}\\}$
cannot be accepted by any DFAwtl. Here we show that with a similar method as
in Example 4.12, DFAwntl is able to accept this language. The automaton is
shown in Figure 1. In each state the indicated set, if any, shows the
translucent letters of the given state. The other notation is standard, e.g.,
double circles for final states, etc.

Figure 1: A DFAwntl accepting
$\\{w\in\\{a,b\\}^{*}~{}|~{}|w|_{a}=|w|_{b}\text{ or }2|w|_{a}=|w|_{b}\\}$.

Last, but not least, we present some closure properties.

######  Proposition 4.13.

The class of languages accepted by NFAwntl is closed under union.

######  Proof 4.14.

Wlog. we may assume that the two languages are over the same alphabet
$\Sigma$. Now, having two NFAwntl, say
$A_{1}=(Q_{1},\Sigma,\$,\tau_{1},I_{1},F_{1},\delta_{1})$ and
$A_{2}=(Q_{2},\Sigma,\$,\tau_{2},I_{2},F_{2},\delta_{2})$ with $Q_{1}\cap
Q_{2}=\emptyset$, we construct $A=(Q_{1}\cup Q_{2},\Sigma,\$,\tau,I_{1}\cup
I_{2},F_{1}\cup F_{2},\delta)$, where
$\tau(q)=\left\\{\begin{array}[]{ll}\tau_{1}(q),&\hbox{if $q\in Q_{1}$;}\\\
\tau_{2}(q),&\hbox{if $q\in Q_{2}$.}\end{array}\right.$ and for each
$a\in\Sigma$,
$\delta(q,a)=\left\\{\begin{array}[]{ll}\delta_{1}(q,a),&\hbox{if $q\in
Q_{1}$;}\\\ \delta_{2}(q,a),&\hbox{if $q\in Q_{2}$.}\end{array}\right.$. Then
$A$ may choose nondeterministically among the possible initial states,
depending on if the chosen state is in $I_{1}$ or $I_{2}$, $A$ will do a
computation that is similar to a computation of $A_{1}$ or $A_{2}$,
respectively.

It is known that the language class accepted by DFAwtl is not closed under
union [31]. On the other hand, we have also seen, that DFAwntl may also be
able to compute the union of some languages accepted by DFAwntl, however, in
general we leave open the problem if this class is closed under union.

On the other hand, the language class of NFAwtl is closed under concatenation,
and the proof was based on guessing when the last occurrence of the letters
are consumed to give a construction when the last occurrence of any letter was
consumed without using any translucency [31]. As in the new model, generally,
we may not be sure when the last occurrence is consumed (maybe even in the
first step), the original construction definitely does not work. Thus, the
closure of the new classes under concatenation is also left as an open
problem.

The fact that each accepted language must have a letter equivalent regular
sublanguage and the examples shown lead also to the following non-closure
property:

######  Proposition 4.15.

Language classes accepted by NFAwntl and DFAwtl are not closed under
intersection with regular sets, and thus they are not closed under
intersection.

##  5 Conclusions

Recently, another extension of the finite automata with translucent letters
was investigated in which in the computation the head is not restarting after
erasing a symbol, but continues from the position where this letter has been
erased (or by reaching the endmarker, it starts from the beginning again)
[16]. This model is defining some new interesting classes of languages that
are superclasses of the classes of languages of the original model, as the new
model is able to simulate the original nondeterministic finite automata with
translucent letters. Our extensions, the FAwntl, are such extensions that the
original deterministic and nondeterministic finite automata with translucent
letters are special cases of our new models (we may not need to simulate them
as they are included in our new classes of automata), thus the computational
power of the original models has been increased by relaxing the condition of
disjointness of the sets of letters for a state which is containing the
translucent letters of the given state and which is containing the letters
that can be read in the given state. However, we left open if nondeterministic
transitions are more powerful in case we allow nondeterministic translucency
(the author guesses/conjectures that the model DFAwntl is weaker than NFAwntl
in terms of accepted languages). It is also left open if DFAwntl are able to
accept all rational trace languages.

Although the expressive power has been increased, the new model still has
various limitations, as the accepted languages must always have a letter
equivalent regular sublanguage. As the class is not closed under intersection
with regular languages, transduced-input variants can be investigated and
studied in the future similarly to [6]. Various closure properties of the new
classes of languages are left open, they are also subjects of future studies.

We believe that the combination of the new directions by continuing the
computation from the position of the erased letter and by using
nondeterministic translucency, can fruitfully be considered also in the
future.

In the other newly investigated model we have applied the state-deterministic
restriction for FAwtl showing that this model is accepting an interesting
family of languages. Combining state-determinism and nondeterministic
translucency and/or the non-returning feature could also be a nice topic for
future research.

## Acknowledgements

The comments of the anonymous reviewers are gratefully acknowledged.

## References

  * [1]
  * [2] Henning Bordihn, Markus Holzer & Martin Kutrib (2005): _Revolving-Input Finite Automata_.  In Clelia de Felice & Antonio Restivo, editors: Developments in Language Theory, 9th International Conference, DLT 2005, Palermo, Italy, July 4-8, 2005, Proceedings, Lecture Notes in Computer Science 3572, Springer, pp. 168–179, 10.1007/11505877_15.
  * [3] P. Cartier & D. Foata (1969): _Problèmes combinatoires de commutation et réarrangements_.  Springer, 10.1007/BFb0079468.
  * [4] Hiroyuki Chigahara, Szilárd Zsolt Fazekas & Akihiro Yamamura (2016): _One-Way Jumping Finite Automata_.  Int. J. Found. Comput. Sci. 27(3), p. 391, 10.1142/S0129054116400165.
  * [5] Volker Diekert & Gregorz (eds.) Rozenberg (1995): _The Book of Traces_.  World Scientific, Singapore, 10.1142/2563.
  * [6] Madeeha Fatima & Benedek Nagy (2020): _Transduced-Input Automata with Translucent Letters_.  Comptes rendus de l’Académie bulgare des Sciences 73(1), pp. 33–39, 10.7546/CRABS.2020.01.04.
  * [7] Rudolf Freund, Gheorghe Paun, Grzegorz Rozenberg & Arto Salomaa (1997): _Watson-Crick finite automata_.  In Harvey Rubin & David Harlan Wood, editors: DNA Based Computers, Proceedings of a DIMACS Workshop, Philadelphia, Pennsylvania, USA, June 23-25, 1997, DIMACS Series in Discrete Mathematics and Theoretical Computer Science 48, DIMACS/AMS, pp. 297–327, 10.1090/dimacs/048/22.
  * [8] M. A. Harrison (1978): _Introduction to Formal Language Theory_.  Addison-Wesley.
  * [9] J.E. Hopcroft & J.D. Ullman (1979): _Introduction to Automata Theory, Languages, and Computation_.  Addison-Wesley, Reading, M.A.
  * [10] Petr Jancar, Frantisek Mráz, Martin Plátek, Martin Procházka & Jörg Vogel (1995): _Restarting Automata, Marcus Grammars and Context-Free Languages_.  In Jürgen Dassow, Grzegorz Rozenberg & Arto Salomaa, editors: Developments in Language Theory II, At the Crossroads of Mathematics, Computer Science and Biology, Magdeburg, Germany, 17-21 July 1995, World Scientific, Singapore, pp. 102–111.
  * [11] Ryszard Janicki, Jetty Kleijn, Maciej Koutny & Lukasz Mikulski (2019): _Classifying invariant structures of step traces_.  J. Comput. Syst. Sci. 104, pp. 297–322, 10.1016/j.jcss.2017.05.002.
  * [12] Radim Kocman, Zbynek Krivka, Alexander Meduna & Benedek Nagy (2022): _A jumping $5’\rightarrow 3’$ Watson-Crick finite automata model_.  Acta Informatica 59(5), pp. 557–584, 10.1007/s00236-021-00413-x.
  * [13] Roussanka Loukanova (2007): _Linear Context Free Languages_.  In Cliff B. Jones, Zhiming Liu & Jim Woodcock, editors: Theoretical Aspects of Computing - ICTAC 2007, 4th International Colloquium, Macau, China, September 26-28, 2007, Proceedings, Lecture Notes in Computer Science 4711, Springer, pp. 351–365, 10.1007/978-3-540-75292-9_24.
  * [14] Alexandru Mateescu, Kai Salomaa & Sheng Yu (2000): _On Fairness of Many-Dimensional Trajectories_.  J. Autom. Lang. Comb. 5(2), pp. 145–157, 10.25596/jalc-2000-145.
  * [15] Alexander Meduna & Petr Zemek (2012): _Jumping Finite Automata_.  Int. J. Found. Comput. Sci. 23(7), pp. 1555–1578, 10.1142/S0129054112500244.
  * [16] Frantisek Mráz & Friedrich Otto (2022): _Non-Returning Finite Automata With Translucent Letters_.  In Henning Bordihn, Géza Horváth & György Vaszil, editors: Proceedings 12th International Workshop on Non-Classical Models of Automata and Applications, NCMA 2022, Debrecen, Hungary, August 26-27, 2022, EPTCS 367, pp. 143–159, 10.4204/EPTCS.367.10.
  * [17] B. Nagy & F. Otto (2011): _Finite-state acceptors with translucent letters_.  In G. Bel-Enguix, V. Dahl & A.O. De La Puente, editors: BILC 2011: AI Methods for Interdisciplinary Research in Language and Biology, Proc.; in ICAART 2011: 3rd International Conference on Agents and Artificial Intelligence, SciTePress, Portugal, pp. 3–13.
  * [18] Benedek Nagy (2008): _On $5^{\prime}\to 3^{\prime}$ Sensing Watson-Crick Finite Automata_.  In Max H. Garzon & Hao Yan, editors: DNA Computing, 13th International Meeting on DNA Computing, DNA13, Memphis, TN, USA, June 4-8, 2007, Revised Selected Papers, Lecture Notes in Computer Science 4848, Springer, pp. 256–262, 10.1007/978-3-540-77962-9_27.
  * [19] Benedek Nagy (2009): _Languages generated by context-free grammars extended by type AB $\rightarrow$ BA rules_.  Journal of Automata, Languages and Combinatorics 14, pp. 175–186.
  * [20] Benedek Nagy (2011): _On CD-Systems of Stateless Deterministic R(2)-Automata_.  J. Autom. Lang. Comb. 16(2-4), pp. 195–213, 10.25596/jalc-2011-195.
  * [21] Benedek Nagy (2012): _A class of 2-head finite automata for linear languages_.  Triangle 8 (Languages. Mathematical Approaches), pp. 89–99.
  * [22] Benedek Nagy (2013): _On a hierarchy of $5^{\prime}\to 3^{\prime}$ sensing Watson-Crick finite automata languages_.  J. Log. Comput. 23(4), pp. 855–872, 10.1093/logcom/exr049.
  * [23] Benedek Nagy (2021): _State-deterministic $5^{\prime}\to 3^{\prime}$ Watson-Crick automata_.  Nat. Comput. 20(4), pp. 725–737, 10.1007/s11047-021-09865-z.
  * [24] Benedek Nagy (2009): _On a hierarchy of $5^{\prime}\to 3^{\prime}$ sensing WK finite automata languages_.  In: Mathematical Theory and Computational Practice, CiE, Abstract Booklet, Heidelberg, Germany, pp. 266–275.
  * [25] Benedek Nagy (2022): _Quasi-deterministic $5^{\prime}\to 3^{\prime}$ Watson-Crick Automata_.  In Henning Bordihn, Géza Horváth & György Vaszil, editors: Proceedings 12th International Workshop on Non-Classical Models of Automata and Applications, NCMA 2022, Debrecen, Hungary, August 26-27, 2022, EPTCS 367, pp. 160–176, 10.4204/EPTCS.367.11.
  * [26] Benedek Nagy & Arif A. Akkeles (2017): _Trajectories and Traces on Non-traditional Regular Tessellations of the Plane_.  In Valentin E. Brimkov & Reneta P. Barneva, editors: Combinatorial Image Analysis - 18th International Workshop, IWCIA 2017, Plovdiv, Bulgaria, June 19-21, 2017, Proceedings, Lecture Notes in Computer Science 10256, Springer, pp. 16–29, 10.1007/978-3-319-59108-7_2.
  * [27] Benedek Nagy & László Kovács (2014): _Finite Automata with Translucent Letters Applied in Natural and Formal Language Theory_.  In: Transactions on Computational Collective Intelligence XVII, Lecture Notes in Computer Science 8790, Springer, pp. 107–127, 10.1007/978-3-662-44994-3_6.
  * [28] Benedek Nagy & Friedrich Otto (2010): _CD-Systems of Stateless Deterministic R(1)-Automata Accept All Rational Trace Languages_.  In Adrian-Horia Dediu, Henning Fernau & Carlos Martín-Vide, editors: Language and Automata Theory and Applications, 4th International Conference, LATA 2010, Trier, Germany, May 24-28, 2010. Proceedings, Lecture Notes in Computer Science 6031, Springer, pp. 463–474, 10.1007/978-3-642-13089-2_39.
  * [29] Benedek Nagy & Friedrich Otto (2011): _An Automata-Theoretical Characterization of Context-Free Trace Languages_.  In Ivana Cerná, Tibor Gyimóthy, Juraj Hromkovic, Keith G. Jeffery, Rastislav Královic, Marko Vukolic & Stefan Wolf, editors: SOFSEM 2011: Theory and Practice of Computer Science - 37th Conference on Current Trends in Theory and Practice of Computer Science, Nový Smokovec, Slovakia, January 22-28, 2011. Proceedings, Lecture Notes in Computer Science 6543, Springer, pp. 406–417, 10.1007/978-3-642-18381-2_34.
  * [30] Benedek Nagy & Friedrich Otto (2011): _Globally Deterministic CD-Systems of Stateless R(1)-Automata_.  In Adrian-Horia Dediu, Shunsuke Inenaga & Carlos Martín-Vide, editors: Language and Automata Theory and Applications - 5th International Conference, LATA 2011, Tarragona, Spain, May 26-31, 2011. Proceedings, Lecture Notes in Computer Science 6638, Springer, pp. 390–401, 10.1007/978-3-642-21254-3_31.
  * [31] Benedek Nagy & Friedrich Otto (2012): _On CD-systems of stateless deterministic R-automata with window size one_.  J. Comput. Syst. Sci. 78(3), pp. 780–806, 10.1016/j.jcss.2011.12.009.
  * [32] Benedek Nagy & Friedrich Otto (2013): _Globally deterministic CD-systems of stateless R-automata with window size 1_.  Int. J. Comput. Math. 90(6), pp. 1254–1277, 10.1080/00207160.2012.688820.
  * [33] Benedek Nagy & Friedrich Otto (2020): _Linear automata with translucent letters and linear context-free trace languages_.  RAIRO Theor. Informatics Appl. 54, p. 3, 10.1051/ita/2020002.
  * [34] Benedek Nagy & Shaghayegh Parchami (2021): _On deterministic sensing $5^{\prime}\to 3^{\prime}$ Watson-Crick finite automata: a full hierarchy in 2detLIN_.  Acta Informatica 58(3), pp. 153–175, 10.1007/s00236-019-00362-6.
  * [35] Benedek Nagy & Shaghayegh Parchami (2022): _$5^{\prime}\to 3^{\prime}$ Watson-Crick automata languages – without sensing parameter_.  Nat. Comput. 21(4), pp. 679–691, 10.1007/s11047-021-09869-9.
  * [36] Benedek Nagy, Shaghayegh Parchami & Hamid Mir Mohammad Sadeghi (2017): _A New Sensing $5^{\prime}\to 3^{\prime}$ Watson-Crick Automata Concept_.  In Erzsébet Csuhaj-Varjú, Pál Dömösi & György Vaszil, editors: Proceedings 15th International Conference on Automata and Formal Languages, AFL 2017, Debrecen, Hungary, September 4-6, 2017, EPTCS 252, pp. 195–204, 10.4204/EPTCS.252.19.
  * [37] Friedrich Otto (2006): _Restarting Automata_.  In Zoltán Ésik, Carlos Martín-Vide & Victor Mitrana, editors: Recent Advances in Formal Languages and Applications, Studies in Computational Intelligence 25, Springer, pp. 269–303, 10.1007/978-3-540-33461-3_11.
  * [38] Shaghayegh Parchami & Benedek Nagy (2018): _Deterministic Sensing $5^{\prime}\to 3^{\prime}$ Watson-Crick Automata Without Sensing Parameter_.  In Susan Stepney & Sergey Verlan, editors: Unconventional Computation and Natural Computation - 17th International Conference, UCNC 2018, Fontainebleau, France, June 25-29, 2018, Proceedings, Lecture Notes in Computer Science 10867, Springer, pp. 173–187, 10.1007/978-3-319-92435-9_13.
  * [39] R. J. Parikh (1961): _Language generating devices_.  MIT Res. Lab., Quarterly Progress Report 60, pp. 199–212.
  * [40] Gheorghe Paun, Grzegorz Rozenberg & Arto Salomaa (1998): _DNA Computing - New Computing Paradigms_.  Texts in Theoretical Computer Science. An EATCS Series, Springer, 10.1007/978-3-662-03563-4.


Max Planck Institute for Physics, Germany S. Wallner on behalf of the COMPASS
Collaboration

# Strange-Meson Spectroscopy with COMPASS

S. Wallnerins:x for the COMPASS Collaboration swallner@mpp.mpg.deins:xins:x

###### Abstract

While the spectrum of non-strange light mesons is well known, many predicted
strange mesons have not yet been observed, and many potentially observed
states require further confirmation.

Using the $K^{-}$ component of the hadron beam at the M2 beamline at CERN, we
study the strange-meson spectrum with the COMPASS experiment. The flagship
channel is the ${K^{-}\pi^{-}\pi^{+}}$ final state, for which COMPASS has
obtained the world’s largest sample. Based on this sample, we have performed
the most detailed and comprehensive partial-wave analysis of this final state
to date. For example, we observe a clear signal from the well-known
$K^{*}_{2}(1430)$, and for the first time we study the $K_{2}(1770)$,
$K_{2}(1820)$, and $K_{2}(2250)$ in a single analysis. We also find evidence
for a supernumerary signal called $K(1630)$, suggesting that this signal is a
pseudoscalar exotic strange meson.

##  1 Introduction

The PDG [1] currently lists only 25 strange mesons, 9 of which still need
confirmation. In addition, many states predicted by quark models are missing.
To establish a complete picture of the light-meson sector, it is important to
find all the strange partners of the non-strange light mesons, i.eto complete
the corresponding SU(3) flavor nonets. This includes the search for exotic
mesons beyond pure quark-model $q\bar{q}$ states.

At COMPASS, we explore the strange-meson spectrum in diffractive scattering of
$190\text{\,}\mathrm{GeV}\text{\,}{\mathrm{\text{$c$}}}^{-1}$ negative kaons
off a liquid hydrogen target. Our flagship channel is the
${K^{-}\pi^{-}\pi^{+}}$ final state, which in principle gives access to all
strange mesons. COMPASS has acquired the so far world’s largest sample of
about $720\,000$ exclusive events for this final state. In section 2 we
briefly introduce the partial-wave analysis method used to analyze this
sample. In sections 3, 4 and 5 we show selected results of this analysis. A
complete discussion of this analysis can be found in ref. [2]

##  2 The Partial-Wave Analysis Method

We performed a partial-wave analysis in two stages to identify strange mesons
appearing in the ${K^{-}\pi^{-}\pi^{+}}$ final state and to measure their
masses and widths.

In the first stage, the data is decomposed into contributions from various
partial waves. The partial waves are represented by
$a={J}^{{P}}\,{M}^{\varepsilon}\,\allowbreak{\zeta}\,{b}\,{L}$, where
$J^{P}M^{\varepsilon}$ are the quantum numbers of the ${K^{-}\pi^{-}\pi^{+}}$
system,111Here, $J$ is the spin of the ${K^{-}\pi^{-}\pi^{+}}$ state and $P$
its parity. The spin projection along the beam axis is expressed in the
reflectivity basis [3] and given by $M^{\varepsilon}$. $\zeta$ is the so-
called isobar, i.ethe intermediate two-body resonance, and $L$ is the orbital
angular momentum between the bachelor particle $b$ and the isobar. To this
end, the distribution in the ${K^{-}\pi^{-}\pi^{+}}$ phase-space variables
$\tau$ is modeled as 222The set of partial waves included in
$\sum_{a,b}^{\text{waves}}$ is inferred from data based on a large pool of 596
allowed waves using regularization-based model-selection techniques. In
addition, a so-called flat wave, which has a uniform distribution in $\tau$,
is incoherently added to the intensity model. Since the flat wave does not
pick up significant intensity, we drop it in eq. 1 for simplicity.

$\mathcal{I}(\tau;m_{K\pi\pi},{t^{\prime}})=\sum\limits_{a,b}^{\text{waves}}\psi_{a}(\tau;m_{K\pi\pi})\rho_{ab}(m_{K\pi\pi},{t^{\prime}})\,\psi_{b}^{*}(\tau;m_{K\pi\pi}).$
(1)

Using the isobar model, we calculate the decay amplitudes $\psi_{a}$
analytically. The spin-density matrix $\rho_{ab}(m_{K\pi\pi},{t^{\prime}})$
represents the production and propagation of the ${K^{-}\pi^{-}\pi^{+}}$
system. To measure its dependence on the invariant mass $m_{K\pi\pi}$ of the
${K^{-}\pi^{-}\pi^{+}}$ system and the four-momentum transfer squared
${t^{\prime}}$ between the beam kaon and the target proton, the decomposition
is performed independently in 75 narrow $m_{K\pi\pi}$ bins and 4
${t^{\prime}}$ bins. No assumption about the resonance content of the
${K^{-}\pi^{-}\pi^{+}}$ system enters at this stage.

In addition to the signal reaction $K^{-}p\to K^{-}\pi^{-}\pi^{+}p$,
backgrounds from other reactions, e.gthe production of the
$\pi^{-}\pi^{-}\pi^{+}$ final state via diffractive dissociation from
misidentified beam pions, leak into the ${K^{-}\pi^{-}\pi^{+}}$ sample. At the
first stage, we effectively take these incoherent backgrounds into account by
modeling them in terms of ${K^{-}\pi^{-}\pi^{+}}$ partial waves. Technically,
this is done by parameterizing $\rho_{ab}$ as a matrix of rank three [2].

In the second stage, we model $\rho_{ab}(m_{K\pi\pi},{t^{\prime}})$ for 14
selected partial waves using physical amplitudes. In this so-called the
resonance-model fit we use an incoherent sum over signal and incoherent
background contributions. Each ${K^{-}\pi^{-}\pi^{+}}$ partial wave $a$ is
modeled as

$\mathcal{T}_{a}(m_{K\pi\pi},{t^{\prime}})=\mathcal{K}(m_{K\pi\pi},{t^{\prime}})\sum\limits_{k}^{\text{comp.}}\mathcal{C}_{a}^{k}({t^{\prime}})\mathcal{D}_{k}(m_{K\pi\pi}),$
(2)

which are coherent sums over various components $k$ that may contribute to
wave $a$. These include resonance components for strange mesons and for each
wave a so-called non-resonant component that accounts for other coherent
production mechanisms leading to the same final state, such as Deck processes.
The dynamic amplitudes $\mathcal{D}_{k}(m_{K\pi\pi})$ of the resonance
components contain relativistic Breit-Wigner amplitudes, whose free parameters
are the mass and width of the resonance. The dynamic amplitudes of the non-
resonant components are parameterized by an empirical function. The coupling
amplitude $\mathcal{C}_{a}^{k}({t^{\prime}})$ represents the strength and
phase of the component $k$ within the partial wave $a$. We used independent
constant coupling amplitudes for each ${t^{\prime}}$ bin. The kinematic factor
$\mathcal{K}(m_{K\pi\pi},{t^{\prime}})$ accounts for the phase-space volume
and the production process.

The $\pi^{-}\pi^{-}\pi^{+}$ background, which is the largest incoherent
background, is modeled by a fixed parameterization that we determined from the
high-precision COMPASS data of the $\pi^{-}\pi^{-}\pi^{+}$ final state [4].
Other incoherent backgrounds are effectively subsumed by a flexible background
parameterization that is fitted to the data.

##  3 Partial-Waves with $J^{P}=2^{+}$

We included the ${2}^{{+}}\,{1}^{+}\,\allowbreak{K^{*}(892)}\,{\pi}\,{D}$ and
${2}^{{+}}\,{1}^{+}\,\allowbreak{\rho(770)}\,{K}\,{D}$ waves in the resonance-
model fit, which both exhibit a clear signal of the well-known
$K^{*}_{2}(1430)$. The resonance-model describes both waves well. Our
determination of the $K^{*}_{2}(1430)$ mass and width agree with previous
experiments with comparably good uncertainties. The consistent observation of
the $K^{*}_{2}(1430)$, despite a significant contribution from the
$\pi^{-}\pi^{-}\pi^{+}$ background to the
${2}^{{+}}\,{1}^{+}\,\allowbreak{\rho(770)}\,{K}\,{D}$ wave, also validates
our analysis approach.

##  4 Partial-Waves with $J^{P}=2^{-}$

We included four partial waves with $J^{P}=2^{-}$ in the resonance-model fit.
Figure 1 shows exemplarily the intensities and relative phases of the
${2}^{{-}}\,{0}^{+}\,\allowbreak{K^{*}_{2}(1430)}\,{\pi}\,{S}$ and
${2}^{{-}}\,{0}^{+}\,\allowbreak{f_{2}(1270)}\,{K}\,{S}$ waves. The
intensities shown in panels (a) and (d) exhibit a peak at about
$1.8\text{\,}\mathrm{GeV}\text{\,}{\mathrm{\text{$c$}}}^{-2}$ accompanied by a
rise of the relative phases shown in panels (c) and (e). Both are well
reproduced by an interference between the $K_{2}(1770)$ and $K_{2}(1820)$
components. However, the relative strength of the $K_{2}(1770)$ and
$K_{2}(1820)$ components is different in the four $2^{-}$ waves. This can also
be seen from the phase difference between the
${2}^{{-}}\,{0}^{+}\,\allowbreak{K^{*}_{2}(1430)}\,{\pi}\,{S}$ and
${2}^{{-}}\,{0}^{+}\,\allowbreak{f_{2}(1270)}\,{K}\,{S}$ waves (b), which is
not constant as expected if both waves had exactly the same resonance content.
By simultaneously fitting the four $2^{-}$ waves, this difference allows to
separate the nearby $K_{2}(1770)$ and $K_{2}(1820)$. We exclude the occurrence
of only one state in the region around
$1.8\text{\,}\mathrm{GeV}\text{\,}{\mathrm{\text{$c$}}}^{-2}$ with a
significance of about $11\sigma$. This is the best evidence for two states so
far.

Figure 1: Intensities (diagonal) and relative phases (off-diagonal) of two
$2^{-}$ waves and the ${1}^{{+}}\,{0}^{+}\,\allowbreak{\rho(770)}\,{K}\,{S}$
reference wave in an exemplary ${t^{\prime}}$ bin. The black points represent
the measured data. The curves represent the result of the resonance-model fit.
The red curves correspond to the total model, the blue curves to the resonance
components, the green curves to the non-resonant components, the orange curves
to the $\pi^{-}\pi^{-}\pi^{+}$ background components, and the brown curves to
the effective-background components. The analytic continuations of all
components beyond the $m_{K\pi\pi}$ fit ranges are shown in lighter colors.

In addition, the intensity spectra exhibit a shoulder at about
$2.2\text{\,}\mathrm{GeV}\text{\,}{\mathrm{\text{$c$}}}^{-2}$ accompanied by a
rising relative phase. Both are well reproduced by the $K_{2}(2250)$
component. For the first time, we studied the $K_{2}(1770)$, $K_{2}(1820)$,
and $K_{2}(2250)$ in a single self-consistent analysis. Our determination of
masses and widths agree with previous observations.

##  5 Partial-Waves with $J^{P}=0^{-}$ and Exotic Strange Mesons

In the pseudoscalar sector, the PDG [1] lists the established $K(1460)$ and
the unconfirmed $K(1830)$. In addition, the PDG lists a $K(1630)$, whose
quantum numbers are actually undetermined. Also, this $K(1630)$ has only been
observed by a single experiment so far with a width of only
$16\text{\,}\mathrm{MeV}\text{\,}{\mathrm{\text{$c$}}}^{-2}$, which is
unusually small for a strange meson.

At COMPASS, we study strange pseudoscalar mesons via their $\rho(770)K$ decay.
The corresponding intensity distribution (fig. 2, left) exhibits a peak at
about $1.4\text{\,}\mathrm{GeV}\text{\,}{\mathrm{\text{$c$}}}^{-2}$, which is
described mainly by the $K(1460)$ component, as expected, and by the
effective-background. However, this partial wave is affected by known analysis
artifacts in the range
$m_{K\pi\pi}\lesssim$1.6\text{\,}\mathrm{GeV}\text{\,}{\mathrm{\text{$c$}}}^{-2}$$,
which are discussed in ref. [2]. This is keeping us from making robust
statements about the $K(1460)$. Hence, we fixed the mass and width of the
$K(1460)$ component in the resonance-model fit to values listed by the PDG.

Figure 2: Intensity spectrum (left) and relative phase (right) of the
${0}^{{-}}\,{0}^{+}\,\allowbreak{\rho(770)}\,{K}\,{P}$ wave in an exemplary
${t^{\prime}}$ bin. Same color code as in fig. 1.

At about $1.7\text{\,}\mathrm{GeV}\text{\,}{\mathrm{\text{$c$}}}^{-2}$, the
intensity distribution exhibits another distinct peak, which is accompanied by
a rise of the relative phase of this wave as shown in fig. 2 (right). The
resonance-model fit yields a significant contribution of the $K(1630)$
component in this region. While the relative phase is reproduced fairly well,
the resonance-model does not perfectly reproduce the intensity spectrum. This
imperfection is caused by the mentioned [2] analysis artifacts. We verified in
detailed Monte Carlo input-output studies and by comparing to well-known
states such as the $K_{4}^{*}(2045)$, for which we observe similar
imperfections in our data (not shown), that the resonance-model fit is not
strongly biased by these imperfections. Thus, we can make robust statements
about the $K(1630)$ from our data. We determined the width of the $K(1630)$ to
be about $140\text{\,}\mathrm{MeV}\text{\,}{\mathrm{\text{$c$}}}^{-2}$, which
is much broader than observed in the previous measurement.

In total, we observe evidence for three excited pseudoscalar states in a
single self-consistent analysis, while quark-model calculations [5] predict
only two states in the mass region below
$2.5\text{\,}\mathrm{GeV}\text{\,}{\mathrm{\text{$c$}}}^{-2}$. The lightest
predicted state agrees best with the $K(1460)$, while the heavier predicted
state agrees best with the $K(1830)$. This suggests $K(1630)$ as a
supernumerary resonance-like signal, making it a candidate for an exotic
strange meson. Measurements of further properties of this signal, such as its
${t^{\prime}}$ dependence, are needed to investigate its nature. These studies
can be carried out partly at COMPASS and at upcoming and planed experiments
such as AMBER.

##  6 Conclusions

Many strange mesons claimed in the past require confirmation, and the search
for exotic strange mesons has only just begun. Based on the world’s largest
sample of the $K^{-}\pi^{-}\pi^{+}$ final state, we performed the most
detailed and comprehensive analysis of this final state to date. We observe
the signal of well-known states such as the $K^{*}_{2}(1430)$ and the
$K_{4}^{*}(2045)$. For the first time, we studied the $K_{2}(1770)$,
$K_{2}(1820)$, and $K_{2}(2250)$ in a single self-consistent analysis.In the
$J^{P}=0^{-}$ sector we find evidence for a supernumerary resonance-like
signal suggesting a pseudoscalar exotic strange meson.

###### Acknowledgements.

The research was funded by the DFG under Germany’s Excellence Strategy -
EXC2094 - 390783311 and BMBF Verbundforschung 05P21WOCC1 COMPASS.

## References

  * [1] R. L. Workman et al. PTEP2022083C0110.1093/ptep/ptac097
  * [2] S. Wallner CERN-THESIS-2021-292 (2021), https://cds.cern.ch/record/2802793
  * [3] S. U. Chung et al. Phys. Rev. D11197563310.1103/PhysRevD.11.633
  * [4] C. Adolph et al. Phys. Rev. D95201703200410.1103/PhysRevD.95.032004
  * [5] D. Ebert et al. Phys. Rev. D97200911402910.1103/PhysRevD.79.114029