headclasses's Introduction
headclasses's People
headclasses's Issues
• page 12, line -8: Setting $m=m-1$ looks strange.
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?
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.
• 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?
section titles are poorly chosen (Section 3 is called "One-way multi-head automata", despite the fact that Definition 3 is about two-way multi-head automata).
section titles are poorly
chosen (Section 3 is called "One-way multi-head automata", despite the fact that Definition 3 is about two-way multi-head automata).
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 13^12 Ultrametric automata and turing machines. -> Ultrametric automata and Turing machines.
• Ultrametric computation is a new area where only very few papers have been published. This improves the papers' chance to be accepted but this demands from the authors to pay more attention to give examples of ultrametric automata. Unfortunately, the authors have not done this.
• 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 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 2 line 8: there should be no space before the dot ending the sentence.
• page 7, line 8: Is it possible to decide for an arbitrary automaton whether the norm converges?
Page 1: the title is somehow misleading. This paper is not about "hierarchy classes", but rather about 2-way multihead ultrametric automata.
verb tenses
verb tenses change between sentences (p. 1: "Balodis et al. have studied .. They show ... ")
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.
• Section 2: $\alpha$ seems to be a non-zero integer number. It is proposed to define $\alpha_p$ here and not in the appendix.
• Section 3: Define $\mathbb{Q}_p$. You are using symbol \$ as endmarker, but later symbol $\vartriangleright$ which is somehow confusing.
• page 7, line 16: In the tuple $M$ you should replace $\Sigma$ by $\Gamma$.
Problems with U_pTMs def and proof
Page 8-9, Definition 5: there must be some missing assumption that the
machine is linearly bounded (it does not write to the right of the
input word); otherwise the positions of the heads are not bounded by
log n, which is used in many places.
Page 10, "space of size O(kn)": the definition of ultrametric
automaton gives that it may accept words of arbitrary length, so here
you cannot simulate the automaton on arbitrary input. But in the
following proofs you use only words of bounded size, so you can
reformulate the simulation result to make it both true and useful in
the construction.
Proof of Theorem 2: Please mention that what is happening here is diagonalization.
Sec. 4.2 and on: in my opinion, all the following material should be completely rewritten: too many models, too sketchy, badly written
• page 1^9-10 Definitions for ultrametric Turing machines and ultrametric multi-register machines are introduced as a tool for proving the results. Comment: definition of a machine is not a tool for proving results
• 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.
Jāpārbauda, vai rindiņas vajadzīgas
Nodaļā 4.2 aiz definition 7
//tik tālu viss labi. bet tad seko:
Additionally a space of size
Pirmkārt, vai tas ir tas pats n? Otrkārt, vai to, kas iekavās vispār vajag? (Varbūt bija saistība ar kkādām nākamajām simulācijām, kur bija reģistru mašīna.. neatceros)
• 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?
• page 5, lines -17ff: Explain the case when the word does not belong to $L_k$ with more details. Why do no more than four lines hold true? It is also not clear to me which role $p$ plays in the proof.
• page 8, Definition 7: Why do you require that the amplitudes are $p$-constructible sets?
• 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.
page 13_19 Ultrametric turing machines -> Ultrametric Turing machines
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.
• Introduction: The concept of ultrametric automata should be better motivated.
• page 7, line 4: Give some explanation why you consider the differences $p_1-p'_1$ ... Explain more detailed why the acceptance is defined as it is.
Nodaļa par p-adiskiem skaitļiem uz appendix
Nodaļa ir izmesta, bet appendixam pievienota nav
• English used in the paper is understandable but clumsy. The authors should consult a specialist.
Problems with Fig. 2
Page 12: the words u (varbūt domāts v?) and h are not defined.
- jābūt v_4, nevis kkādam v_m vai v_{m'} ? Tad kāda nozīme daudzpunktēm?
the Authors should much more stress the possible advantages of their approach and give the proper context to understand their results. E.g. in Sec. 4.3 it is proved that languages recognizable by multihead ultrametric automata have similar structure to languages recognizable by probabilistic, nondeterministic and deterministic automata. Were we to expect something different? Any answer to this question is welcome.
the Authors should much more stress the possible advantages of their approach and give the proper context to understand their results. E.g. in Sec. 4.3 it is proved that languages recognizable by multihead ultrametric automata have similar structure to languages recognizable by probabilistic, nondeterministic and deterministic automata. Were we to expect something different? Any answer to this question is welcome.
• This work as 13 pages including references. In case of acceptance the authors have to shorten the work by one page
• page 13_8 ITA, 14(1):67{82, 1980. -> RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Volume: 14, Issue: 1, page 67-82, 1980
• 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.)
Intro: p-adics
pg.3, Sec. 2.2: the notion of ultametrics is referred to metrics in general and not to norms (which is a particular metric). The three lines before Def.1 should be moved after the notion of metric.
• page 13^11 Problemy Peredachi Informatsii, 15(3):99{106, 1979. -> either " Problems of Information Transmission, 1979, 15:3, 235–241 " or " Problemy Peredachi Informatsii, 15(3):99-106, 1979 (in Russian) "
missing words
sentences are missing words (e.g., on p. 6: "The automaton starts its
in n different starting states .." ),
Intro, pg.1, third paragraph of the Introduction: rewrite in more details
pg.1, third paragraph of the Introduction: rewrite in more details
Page limit
The Authors exceed maximal paper lenght by 3 pages. In order to shorten the manuscript discussion of p-adic numbers in subsection 2.1 can be ommitted altogether, therefore revision is suggested.
• page 10, -6 and Figure 2: The figure gives no information on how the contents of a Turing machine are simulated with registers.
• page 10, line 10-12: Give some more details here.
First sentence
First sentence gives the Turing machine credit to a 2012 paper and not to Turing 1936? or maybe it is an English issue.
• page 9, first paragraph: The explanation is too vague. The claim should be stated explicitly and proved in detail.
Problems with Fig. 1
pg.7, Fig.1: even in this case, the reader must figure out the meaning of edge labels
Jāsaraksta bildes apraksts
Page 7 lines 18-20, "We require [...] sums converge [...]": This is a very strange condition. Can you at all decide whether it is satisfied?
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.