Related Issues (20)
- • page 10, line 10-12: Give some more details here. HOT 1
- • page 10, -6 and Figure 2: The figure gives no information on how the contents of a Turing machine are simulated with registers.
- • page 12, line -8: Setting $m=m-1$ looks strange. HOT 1
- • This work as 13 pages including references. In case of acceptance the authors have to shorten the work by one page
- • Add an example as indicated above (But the authors do not give an (even just theoretical) example showing why p-ultrametric automata could be useful in CS. Perhaps the results of Balodis et al. [1] are the main motivation, but this is not clear.)
- • After definition 4 ($p$-ultrametic $k$-head finite automata) you require the possibly infinite sums to converge for every word. I assume you mean conversion in the $p$-adic norm. Is this a decidable property?
- • In definition 5 ($p$-ultrametric Turing machine) you state, that a $u_ptm$ accepts a word if it stops in an accepting state. But right in the next sentence you say the acceptance criteria is similar to the criteria for $2u_pfa(k)$, which involves comparing the sum of the norms of the amplitudes of all accepting states to a threshold value. Maybe you mean classical Turing machines in the first sentence and $p$-ultrametric ones in the second?
- • As the acceptance condition for $u_ptm$ was unclear to me, I had trouble understanding the end of the proof of theorem 2: You define the acceptance of $\mathcal{T}$ to be inverse to the acceptance of $\mathcal{A}$, but this way you only change which states contribute to the output amplitude and you do not change directly which words are accepted.
- • In the proof of lemma 1, why do you assume that $\mathcal{T}$ uses exactly two tapes and that the size of the second tape's contents is logarithmically bounded? It seems like you assume $\mathcal{T}$ to be one of the $u_ptm$ you constructed earlier to simulate a $u_pfa(k)$. If this is the case, you should state it.
- • Maybe it is hidden in the details, but I have not found any point where the usage of the $p$-adic norm actually matters. Do your results still hold if one replaces $p$-adic numbers by the reals and $p$-adic norm by the absolute value?
- Page 1: the title is somehow misleading. This paper is not about "hierarchy classes", but rather about 2-way multihead ultrametric automata. HOT 1
- Page 1, abstract: the abstract is not well thought-out. You do not explore probabilistic automata, and the word "hierarchy" definitely should occur in the abstract.
- Page 2 line 8: there should be no space before the dot ending the sentence.
- Page 2 line 10: you use wrong dashes. \textendash (--) is meant for page ranges like 1--10. You should use \textemdash (---) as a punctuation dash --- like this. The same happens on Page 4. HOT 1
- Page 3 line 14: "2n f a(k)" looks ugly. You should replace it with "2\mathit{nfa}(k)". The same problem occurs in "df a" and "u_pf a"
- Page 7 lines 18-20, "We require [...] sums converge [...]": This is a very strange condition. Can you at all decide whether it is satisfied?
- Page 8 line -15, "exactly the same words as the automaton": this is not true. In the construction on page 9 you reserve only n bits for a position of a head, so you are limited only to words of length bounded by 2^n. On Page 9 line 2 you cannot assume that the length of the input word does not exceed 2^n. But I believe this can be easily repaired: the constructed machine can deterministically read the input word and reserve an appropriate amount of space before starting the simulation.
- Page 10 line 2, "Contrary to the previous description": what description do you mean? The one in section 4.2 did not include the input for A.
- Page 11, end of proof of Lemma 1: does the constructed automaton satisfy the condition on the convergence of the sum mentioned after Definition 4?
- Jāiespiež iekš 12 lpp
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from headclasses.