key: cord-0043243-eveoyytw
authors: Uçan, Ahmet Bilal
title: Limited Two-Way Deterministic Finite Automata with Advice
date: 2020-01-07
journal: Language and Automata Theory and Applications
DOI: 10.1007/978-3-030-40608-0_15
sha: 64da240d834ad271f8500244a663824560f74ee8
doc_id: 43243
cord_uid: eveoyytw

External assistance in the form of strings called advice is given to an automaton in order to make it a non-uniform model of computation. Automata with advice are then examined to better understand the limitations imposed by uniformity, which is a typical property shared by all feasible computational models. The main contribution of this paper is to introduce and investigate an extension of the model introduced by Küçük et al. [6]. The model is called circular deterministic finite automaton with advice tape (cdfat). In this model the input head is allowed to pass over input multiple times. The number of allowed passes over the input, which is typically a function of input length, is considered as a resource besides the advice amount. The results proved for the model include a hierarchy for cdfat with real-time heads, simulation of 1w/1w cdfat by 1w/rt cdfat, lower bounds of resources provided to a cdfat in order to make it powerful enough to recognize any language, utilizable advice limit regardless of the allowed pass limit, a relation between utilizable pass limit and advice limit, and some closure properties.

Advised computation, where external trusted assistance is provided to a machine to help it for computational tasks, was introduced by Karp and Lipton [4] in 1982. Damm and Holzer [1] considered giving advice to restricted versions of Turing machines. Recent work on finite automata with advice include the papers of Yamakami [8] [9] [10] [11] , Tadaki et al. [7] , Freivalds et al. [3] , Küçük et al. [6] andĎuriš et al. [2] . Today, there are many different models in literature, partly because of the several options available for a machine to access its advice. However, all such models share some common properties. There is an advice function, which maps input lengths to advice strings and not needed to be computable. Advice strings are composed of characters from an advice alphabet. The machine has to use the same advice string when operating on inputs of the same length. We investigate the class of languages recognized by a machine when it consults some advice function having some bounded growing rate. We then play with that upper bound to see what happens to the aforementioned class. An advised automaton takes advantage of an advice string by reading the character under the advice head and choosing appropriate transition from its transition function accordingly. So the same machine may recognize different languages using different advice functions.

We focus on the advice tape model introduced by Küçük et al. in [6] . Since that model becomes extremely powerful (able to recognize all languages) when allowed to use a 2-way input head, and is remarkably limited for the 1-way head case, [2, Theorem 2] , [6, Theorem 13], we examine a limited version of two-way input access.

Some common terminology to be used in this paper are as follows: n denotes input length, M denotes an automaton, L denotes a language, h denotes an advice function, w denotes a string, Σ denotes input alphabet, Γ denotes advice alphabet, means any, ALL denotes the set of all languages, and |w| c denotes the number of occurrences of character c in string w.

Here are some definitions of concepts that will be used in our discussion, Definition 1 [6] . w 1 ≡ L,n,k w 2 ⇐⇒ w 1 ,

We call L R a prefixsensitive language for relation family R. Definition 3. We call L a prefix-sensitive language iff there exists a relation family R such that L R is a prefix-sensitive language for relation family R.

We defined this model and decided to work on it because the model seems to provide a smooth passage from one-way input head to two-way input head. The name of the new model is circular deterministic finite automaton with advice tape (cdfat) which may have real-time or 1-way input and advice heads (4 possible versions). Circular machines read their input circularly, that is, when the input endmarker has seen and the next transition dictates machine to move its input head to right, the input head immediately returns to the beginning position. Advice head is not allowed to perform such a move.

Note that when restricted to a single pass on input, this model is exactly the same with the standard deterministic finite automaton with advice tapes model (except the two-way input head version) introduced by Küçük et al. [6] .

A circular deterministic finite automaton is a 9-tuple (Q, Σ, Γ, T I , T A , δ, q 0 , q acc , q rej ) where (i) Q is a finite set of internal states, (ii) Σ is a finite set of symbols called the input alphabet that does not contain the endmarker symbol, $, such that $ / ∈ Σ and Σ = Σ ∪ {$}, (iii) Γ is a finite set of symbols called advice alphabet that does not contain the endmarker symbol, $, such that $ / ∈ Γ and Γ = Γ ∪ {$}, (iv) T I ∈ {{S, R}, {R}} represents the set of allowed input head movements where S and R means stay-put and right respectively, (v) T A ∈ {{S, R}, {R}} represents the set of allowed advice head movements where S and R means stay-put and right respectively, (vi) q 0 ∈ Q is the initial state on which the execution begins, (vii) q acc ∈ Q is the accept state on which the execution halts and accepts, (viii) q rej ∈ Q is the reject state on which the execution halts and rejects,

implies that when the automaton is in state q 1 ∈ Q and it scans σ ∈ Σ on its input tape and γ ∈ Γ on its advice tape, a transition occurs which changes the state of the automaton to q 2 ∈ Q, meanwhile moving the input and advice tape heads in the directions specified respectively by t I ∈ T I and t A ∈ T A , A cdfat M = (Q, Σ, Γ, T I , T A , δ, q 0 , q acc , q rej ) is said to accept (reject) a string x ∈ Σ * with the help of an advice string a ∈ Γ * if and only if M , when started at its initial state q 0 with x$ on the input tape and a$ on the advice tape and while the tape heads scan the first symbols, reaches the accepting (rejecting) state, q acc (q rej ), by changing states and moving the input and advice tape heads as specified by its transition function, δ.

A language L defined on the alphabet Σ, is said to be recognized by such a cdfat A language L is said to be recognized by a cdfat, M, using O(g(n))-length advice if there exists an advice function h with the following properties:

-|h(n)| ∈ O(g(n)), and -M recognizes L with the help of h(n).

A language L is said to be recognized by a cdfat, M, using f (n) passes over the input if and only if during the execution of any input of length n, transitions of the form δ( , $, ) = ( , R, ) are used at most f (n) times in total.

Note that it is not allowed for a cdfat to have a transition of the form δ( , , $) = ( , , R), however, there can be transitions δ( , $, ) = ( , R, ). The endmarker of the input is for informing the machine. It may be a different model if we omit it, for the sake of backward compatibility we continue to use it.

For the notational purposes, L{rt − f (n)} denotes the set of languages recognized by cdfat with real-time heads, (n + 1)f (n) length advice and f (n) passes. When a head is allowed to stay-put on its tape, we use a different notation. For instance L{1 − [f (n)]/g(n)} denotes the set of languages recognized by cdfat with 1-way input head and real-time advice head, using g(n) length advice and f (n) passes.

Proof. Assume that for some language L it holds that for all k ∈ N, there exists n ∈ N such that ≡ L,n,k has |Σ| k equivalence classes. Let f be a function which maps any k ∈ N to an n so that ≡ L,n,k has |Σ| k equivalence classes. Define an infinite family of relations

Because if there were no such y for some x 0 and x 1 , then x 0 ≡ L,f (k),k x 1 would be true and the number of equivalence classes would not be |Σ| k . According to the Definition 2, we concluded that L is prefix-sensitive.

For the other direction, let L be a prefix-sensitive language. According to the Definition 2,

Because if the number of equivalence classes of ≡ L,k+f (k),k is less than |Σ| k for some k, then there would be two strings x 0 and x 1 such that

Proof. Let h(n) = w 1 c 1 w 2 c 2 . . . w |Σ| n c Σ n where each w i is a distinct input word of length n and each c i / ∈ Σ is either the accept or the reject symbol. Devise a machine M such that, it tries to match the input word and advice character by character in real-time execution. If a mismatch occurs while trying to match the input word, machine M will advance its input head until it is at the beginning position again. Note that the advice head will be at the first character of the next word on advice at the end of this process. Then it tries to match the next word and so on. At some point matching ends with success, that is, machine M will see the endmarker of input while trying to match the characters. At that point it will accept or reject the string depending on which c i character it is seeing on the advice.

Proof. The idea is that for any given machine M , one can devise a new machine M such that M uses k times less passes than M for all n and for an arbitrary k ∈ N, and still recognizes the same language with the help of some other advice function. Let us group the passes of machine M so that i th group consists of passes from (i − 1)k + 1 to ik. With a single pass, machine M simulates a group of k passes of M . First pass simulates the first group and second pass simulates the second group and so on. Since M does not know which state to begin with a pass without knowing the result of the previous one, it simulates all possibilities and remembers the final state of the previous group of passes using again its states. Therefore the size of the state set of M is s ks+1 where s is the number of states of M .

The new advice function h is a compressed version of the old one. Let Γ be the new advice alphabet whose symbols represent the k permutations of the symbols of Γ . |Γ | = |Γ | k holds. Let |h (n)| = |h(n)|/k for all n > 0. Note that without loss of generality we assume that |h(n)| is an integer multiple of k. We prepare the new advice strings so that h (1) represents all strings from h(1) to h(k), h (2) represents all strings from h(k + 1) to h(2k) and so on.

Proof. Let M 1 , M 2 be machines recognizing L 1 , L 2 with the help of advice functions h 1 , h 2 respectively. Let M 3 be the machine which is claimed to recognize the concatenation language L 1 L 2 with the help of advice function h 3 . The idea is to predict the words w 1 ∈ L 1 and w 2 ∈ L 2 such that w 1 w 2 is the input word. Machine M 3 doesn't know from where to divide the input, so it just tries all the possibilities. We replace the advice characters whose locations correspond to the last character of the first portion of the input with their marked versions in order to inform the machine M 3 .

In the first pass over the input, machine M 3 first simulates M 1 on the first portion of the input and stores the last internal state of that execution. Then it simulates M 2 on the rest of the input and stores the last state of that execution too. Then it begins the second pass simulating M 1 again but this time starting from the last saved state of that thread and when it completes, M 3 will update the last state of the thread and so on. Throughout the execution of M 3 , two separate threads of execution are simulated at the same time. At the end of at most f (n) passes, if both threads end with accepting their respective sub-inputs, M 3 accepts the input. Otherwise, M 3 continues the computation with a different division of the input. Note that, given an input word of length n, there are n + 1 different pairs of words such that their concatenation is the input word. At the end of at most (n + 1)f (n) passes, if no division works, M 3 rejects the input. According to the Theorem 3, asymptotic rate of the passes is the important part so nf (n) passes can do the same job.

Note that we should double the old advice alphabet size and introduce marked versions of the old symbols in order to mark the position of input separation on the advice h 3 . Also note that advice string h 3 (n) will be an interleaved version of the h 1 (k) and h 2 (n − k) concatenated for all k ∈ [0, n] Z . Proof. Let s = |Q| and let Q = {q 1 , q 2 , . . . q s−2 } be the set of all states except the accept and reject states. Let α w,i : Q → Q be a mapping which maps the internal state of machine when input head is for the first time on the first character of w and advice head is at the i th position to the internal state of machine when input head is for the first time on the first character right after the w. Besides its parameters w and i, this mapping depends on the content of the advice and transition function of the machine. Here we consider a single machine working on inputs of the same length n therefore the mapping depends only on its parameters.

Consider execution of a real-time circular machine on two different inputs of length n, namely w 1 z and w 2 z. If we can find two words w 1 and w 2 such that α w1,i = α w2,i for all i ∈ {1, 1 + (n + 1), . . . 1 + (f (n) − 1)(n + 1)} then the two inputs must have the same fate for all z.

Given a single i, there are less than s s distinct functions α w,i . Considering all f (n) functions mentioned above for a word w, there are less than (s s ) f (n) different permutations. Assuming that the number of equivalence classes of relation ≡ L,n,k is greater than (s s ) f (n) for some k and n, there would be two words w 1

and w 2 such that they are in different equivalence classes and have all the same mappings. This is a contradiction.

Proof. Consider the language family L ρ = {w ρ(|w|) | w ∈ Σ * , ρ : N → N}. Note that ρ is assumed to be a non-decreasing function and the input length n = |w|ρ(|w|). Inputs consist of repetitions of a substring w. Define φ(mρ(m)) = m for all m ∈ N + . Depending on the choice of ρ, φ(n) ∈ ω(1) ∩ O(n). We will give three lemmas. Two of them show a hierarchy for the range ω(1) ∩ O(n) and the last one is to put the Θ(1) in.

Since given the input length n and the function ρ we can deduct the period of input, we can check a position of the repeating substring w for each pass. Therefore our machine will need |w| = φ(n) many passes. The advice strings are of the form (parentheses are meta-characters),

Our machine will first search for the first 1 on advice tape and when it has been found, the machine saves the corresponding input character in its states and continue searching for the next 1. When it sees the next 1 it checks the corresponding input character with the one it saved before. If they mismatch input is rejected. The machine then continue searching for 1s and do the same checking till the end of the first pass. It then start with the second pass and do the same procedure again, checking the equality of next character position in substring w. If the endmarker of advice is reached, input is accepted.

Proof. Let M 1 , M 2 be machines recognizing languages L 1 , L 2 with the help of advice functions h 1 and h 2 respectively. Devise a new advice function,

for all n where # is a brand new advice character that occurs nowhere else. Let M 3 be the machine recognizing the union language with the help of h 3 . Machine M 3 first simulates the M 1 and during this simulation it treats the # character in advice as an endmarker. When this simulation ends, which may take at most f (n) passes over the input, M 3 stores the result in its states and start simulating M 2 after adjusting its heads to proper positions, that is input head to the beginning and advice head to the next character after #. After at most f (n) passes over the input, it completes the execution and store the result in its states. In this way it may end up in 4 different states for 4 possible acceptance status of M 1 and M 2 . Via combining some of those states into the accept state and the rest into the reject state; union, intersection or difference of L 1 and L 2 are all recognizable.

Proof. The proof is an easy modification of the proof given byĎuriš et al. for [2, Theorem 3] .

Proof. Consider the execution of an s-state cdfat with one-way heads. Pausing the advice head, passing on the input more than s times forces the machine to enter an infinite loop. Thus, a machine must advance its advice head before that threshold. Therefore at most sg(n) passes are possible for an execution which eventually halts.

For any functions f, g :

Proof. It is possible to simulate the one-way advice head with real-time advice head using additional advice. The idea is to replicate each advice character (n+1)f (n) times and use separator characters # to mark the transition locations. That is, for all n,

where c i ∈ Γ for all i ∈ {1, 2 . . . k} and the c $ is a new advice character which is for repeating the endmarker (it is not allowed to have more than one real endmarker character). When the new machine reads c $ on h , it behaves exactly like the old machine seeing endmarker on h.

Instead of stay-putting advice head in old machine, let it move right one step in new machine. Instead of moving advice head one step in old machine, enter a subprogram which takes advice head to the next # character in new machine.

This trick works because a cdfat with one-way heads must forward its advice head within (n + 1)f (n) computational steps. This is because without loss of generality we can assume at least one head is moving in each step and of course input head can move at most (n + 1)f (n) times in an execution.

It is already known that dfat with 2-way input head is equal in power with the prefix advice model when provided with constant advice [5, Theorem 3.8 ]. Since our model is sandwiched in between the 2-way input model and advice prefix model when it comes to power, we deduce that

Therefore an interesting question to ask is what is the minimum advice for which more passes over input enlarges the class of languages recognized. Küçük and others showed that when provided with polynomial advice, 2-way input head is more powerful than 1-way head [6, Theorem 14] . We proved a stronger result and gave an ultimate answer to the aforementioned question. It turns out that even 2 passes over input is more powerful than a single pass when the machine is provided with an increasing advice.

Theorem 10. Let f : N → N be any function in ω (1) .

Proof. Consider the language family L ρ = {w|w ∈ {1, 2, 3} * , |w| 1 = |w| 2 = ρ(|w|)}. The following two lemmas establish the proof. classes, [6, Lemma 6] . It can be shown that for all n, there exists k ≤ n such that ≡ Lρ,n,k has Θ(ρ 2 (n)) equivalence classes. Since ρ(n) ∈ ω(1) =⇒ ρ(n) ∈ o(ρ 2 (n)), we conclude that

Proof. The idea is to devise a machine which in first pass counts the character 1 and in second pass counts the character 2. Let L 1 = {w|w ∈ {1, 2, 3} * , |w| 1 = ρ(|w|)} and L 2 = {w|w ∈ {1, 2, 3} * , |w| 2 = ρ(|w|)}. Observe that L 1 or L 2 can easily be recognized by a cdfat with a single pass. In order to recognize L 1 for instance, let h(n) = 1 ρ(n) be the advice function, then consider a machine which stay-puts its advice head when it sees a character other than 1 on its input and advances its advice head when it sees 1 on input. It will accept a string iff both endmarkers are read at the same time. L 2 can be recognized similarly. Since

Then for all n and for all k smaller than n, ≡ L,n,k has 2 O(g(n) log g(n)) equivalence classes.

Proof. Define a configuration c i of a machine to be the pair of internal state and advice position. Define a non-stopping configuration c = (q, m) of a machine to be any configuration where q is a state other than accept and reject states. Let C = {c 1 , c 2 , . . . , c (s−2)(g(n)+1) } be the set of all non-stopping configurations for a machine and for input length n (s = |Q|). Without loss of generality assume our machines always end their execution when input head is on the endmarker. Let w be a substring of input (not containing the endmarker) and let α w : C → C be a mapping which maps the configuration of machine when the first character of word w is read first time on input tape to the configuration of machine when the character right after the word w is read first time on input tape. Function α depends on transition function of the machine, the specific word w being processed and the advice content. We focus on a single machine and inputs of the same length n, therefore in our case α depends only on w.

Consider execution of a circular machine on two different inputs of length n, namely w 1 z and w 2 z. Both inputs start execution at the initial configuration and after each pass they start with a new configuration. If we can find two words w 1 and w 2 such that α w1 = α w2 then the two inputs w 1 z and w 2 z must have the same fate for all z.

There are less than 2sg(n) 2sg(n) distinct functions α. Assuming that the number of equivalence classes of ≡ L,n,k is greater than 2sg(n) 2sg(n) for some k and n, there would be two words w 1 , w 2 in two different equivalence classes such that they have the same mapping. This is a contradiction. [6] given access to unlimited advice. According to Theorem 5, a prefix-sensitive language is in L{rt − f (n)} no matter how slow f (n) grows. However we know fromĎuriš et al. [2, Theorem 2] that no prefix-sensitive language is in L{1 − [1] 

On the other hand, as stated in proof of Lemma 6, the language L = {w|w ∈ {1, 2, 3} * , |w| 1 = ρ(|w|)} can be easily recognized by a machine with one-way heads, given access to Θ(ρ(n)) length advice. It is easy to see that for all n, there exists k such that ≡ Lρ,n,k has Θ(ρ(n)) equivalence classes. When the ρ(n) is selected to be linear in n, according to Lemma 1, L / ∈ L{rt − f (n)}. Therefore

An interesting question to ask is what is the minimum advice or pass needed in order for a model to recognize any language. We can show some lower bounds using Lemmas 1 and 7. P AL is the language of even palindromes. 

We showed that cdfat with real-time heads can utilize up to linearly many passes over input. We showed that with exponential pass, the real-time machine can recognize any language. However we do not know if the machine can utilize more than linear passes. There may be a clever algorithm for recognizing any language with linear passes. We showed that even the most powerful version of the cdfat, that is the one having one-way input and advice heads, cannot recognize some languages when there is not enough advice (a nearly linear bound). However we are not aware of an algorithm for this machine which uses less than exponential resources to recognize any language. It would be nice to know the minimum amount of resources needed to recognize any language.

We compared the class of languages recognized by single pass deterministic finite automaton with one-way heads and unlimited advice with the growing class of languages recognized by a real-time cdfat as we allow more passes over input. Since we know that the former class is bigger than the latter when we allow only constant amount of pass over input and the reverse is true when we allow exponential passes over input, we wonder how that growing takes place and is there any pass limit for which the two classes are equal. It turned out that this is not the case. As long as the allowed pass limit is not constant and sub-logarithmic, two classes are not subsets of each other. However we do not know exactly when the latter class encompasses the former one.

Automata that take advice

Determinism and nondeterminism in finite automata with advice

Amount of nonconstructivity in deterministic finite automata. Theoret

Turing machines that take advice

Finite and small-space automata with advice

Finite automata with advice tapes

Theory of one-tape linear-time turing machines

Swapping lemmas for regular and context-free languages with advice

The roles of advice to one-tape linear-time turing machines and finite automata

Immunity and pseudorandomness of context-free languages. Theoret

One-way reversible and quantum finite automata with advice

Acknowledgements. Thanks to Prof. Cem Say who have helped editing the paper and correcting my mistakes and to my family for their constant support and love.