<p>Regarding probabilistic (and quantum) automata, you may start by digging this survey: <a href="https://arxiv.org/abs/1507.01988" rel="nofollow noreferrer">https://arxiv.org/abs/1507.01988</a></p>

<p>For very recent results on quantum automata, you may check two recent works by Zachary Remscrim: <a href="https://eccc.weizmann.ac.il/author/659/" rel="nofollow noreferrer">https://eccc.weizmann.ac.il/author/659/</a></p>

<p>Palindrome is an (exclusive) stochastic language, but a probabilistic machine requires log-space to recognize it with bounded error. Two-way quantum automata recognizes palindrome language with bounded-error in super-polynomial time.</p>

CC BY-SA 4.0
2020-03-02T08:33:34.657Z
2020-03-02T08:33:34.657Z
Abuzer Yakaryilmaz
<p>I'm a grad student in math. I'm unaware of available literature in theoretical computer science, so require suggestions for books. Here are the two topics I'm interested in exploring.</p>

<p>1) A complete treatment of palindrome language with reference to finite automata, particularly interested in how a probabilistic finite automate would recognize palindrome language. </p>

<p>2) A thorough treatment of context-sensitive languages. Introductory books don't discuss it in details as it is perhaps not a topic to be studied in a first course. </p>

<p>it appears that introductory books have rather sketchy discussions of the topics, mostly end of chapter problems. Any suggestion is greatly appreciated. </p>

<automata-theory><probabilistic-automata>
Palindrome language and Finite Automata Machines
Muhammad Adeel
# Palindrome language and Finite Automata Machines

(Asked by: username_0 on 2020-03-01)

I'm a grad student in math. I'm unaware of available literature in theoretical computer science, so require suggestions for books. Here are the two topics I'm interested in exploring.

1) A complete treatment of palindrome language with reference to finite automata, particularly interested in how a probabilistic finite automate would recognize palindrome language.

2) A thorough treatment of context-sensitive languages. Introductory books don't discuss it in details as it is perhaps not a topic to be studied in a first course.

it appears that introductory books have rather sketchy discussions of the topics, mostly end of chapter problems. Any suggestion is greatly appreciated.

**Tags:** automata-theory, probabilistic-automata

---

## 1 answers

### Answer by username_1 on 2020-03-02. Score: 1

Regarding probabilistic (and quantum) automata, you may start by digging this survey: <https://arxiv.org/abs/1507.01988>

For very recent results on quantum automata, you may check two recent works by Zachary Remscrim: <https://eccc.weizmann.ac.il/author/659/>

Palindrome is an (exclusive) stochastic language, but a probabilistic machine requires log-space to recognize it with bounded error. Two-way quantum automata recognizes palindrome language with bounded-error in super-polynomial time.


---

