Theoretical Studies on Recognizing Languages
Various models such as Deterministic Turing Machines, Probabilistic Models, and Quantum Classes are explored for recognizing languages, with discussions on regular, nonregular, and uncountable languages. Theoretical concepts like bounded-error recognition, computational complexities, and enumeration techniques are examined in detail.
- Theoretical Studies
- Language Recognition
- Deterministic Turing Machines
- Probabilistic Models
- Quantum Classes
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Maksims Dimitrijevs, Abuzer Yakary lmaz
2DFAs, 2NFAs and even 2AFAs can recognize only regular languages. R si Freivalds has shown that 2PFAs can recognize nonregular languages with bounded error, but in this case they require exponential expected-time. 2QCFAs can do it in polynomial expected time.
Deterministic Turing machines can recognize only countable many languages. We can write the program of TM in binary, and then enumerate all possible programs in ascending lexicographical order. 0
Probabilistic or quantum models can be defined with uncomputable transition values and therefore their cardinalities are uncountably many. 1
What probabilistic and quantum classes that contain uncountable many languages? are the minimal bounded-error 1
?4?|?? ? can be recognized by PTM with bounded error (???? space is required). Bounded-error recognize ????? ?? ??? log8( ??) ? ????? ?? = ???7??7 8??7 82? ??7 8?|? 0 polynomial-time ????? ?? ? = 2QCFA ? ?,? |? , can where
We order the elements of lexicographically and then represent the ?-th element by (?), where the first value (1) is the empty string. (log64?)
Error bound (0 <1/2): if ? ?, it is accepted with pr. 1 if ? ?, it is accepted with pr. :? ? , , , ,
Let ? = ?1?2?3 be an infinite binary sequence. If a biased coin lands on head with probability ? = 0.?101?201?301 , then the value ?? can be determined with probability3 4 after 64? coin tosses.
? ? = ?101?201??01?2?01 = ? 64? ?? ? ?[?] 8? ? ? 1 64? 1 8?2 4 ?101?201 ??01 ?2?01 8? ?101?201 ??00 8? ?101?201 ??01 ?2?01 + 8? ?101?201 ??10 8?
??75 = ??|? > 0 ??? ? ? ?? ? ????? ?? 2 ??75 = ??|? > 0 ??? ? ? ?? ? ????? ?? 64 ? ? = min ? ? ???? ??? ?????? ? ??= 0.?101?201?301 ??01 , ??= 1 = ?|? ?+ , cardinality of is 1 ??75 (?) = ??|? ??75 ??? (log64(?(?))) ? ? ?
We compute ?(?) deterministically. If ? ? = 64? for some ?, we proceed with probabilistic check. We perform ? ? coin tosses and keep the result on work tape. To check, whether (log64(?(?))) ? or not, we need to get the value of ??: (3 ? 2)-th bit after decimal point.
For any binary language ? 0,1, we define another language ???(?) as follows: ??? ? = 0 1?10211?20221?3023 02? 11??02?| ? = ?1?2?3 ?? ? Fact. If a binary language ? is recognized by a bounded-error PTM in space ?(?), then the binary language ???(?) is recognized by a bounded- error PTM in space log ? ? .
Language ????(??75(?)) for ? > 0 can be recognized by a bounded-error PTM in space ?(????+2(?))
???? = 0201021102211023?+1??????+???023?+311026?| ? > 0 ???? ? = ? 0,1 10?|? > 0, ? ????,??? (log64?) ? ?101?201 ?? 23?+2
Theorem. ???(???? ? ) can be recognized by a bounded- error 2PCA that uses ?(????) space on the counter. ??? ????(?) = 0 1?10211?20221?3023 02? 11??02?| ? = ?1?2?3 ?? ????(?) For any ? , the language
Language ????(????(?)) for ? > 0 can be recognized by a bounded-error 2PCA in space ?(????+2(?))
UPOWER64 = 026?|? > 0 recognize with ???? space in a straightforward way. ??????64 ? = 0? 0? ??????64 ??? (log64?) ? - 1DTM can
??75 = ??|? > 0 ??? ? ? ?? ? ????? ?? 64 ??75 (?) = ??|? ??75 ??? (log64(?(?))) ? Polynomial time
???? = 0201021102211023?+1??????+???023?+311026?| ? > 0 ???? can be recognized by sweeping PCA in three passes. ???? ? = ? 0,1 10?|? > 0, ? ????,??? (log64?) ? Subquadratic time: ? 23?? 26?= ? 29?= ?(? ?).
Two-way finite automaton with quantum and classical states, which can use unitary operators and projective measurements on the quantum part. A superoperator, determined by the current classical state and the symbol being scanned on the input tape, is applied to the quantum register, yielding an outcome. Then, the next classical state and tape head movement direction is determined by the current classical state, the symbol being scanned on the input tape, and the observed outcome.
????? ?? = ???7??78??782???78?|? 0 This language can be recognized by a restarting rtQCFA with bounded error.
?? 8?+1, ??= 1, if ? ?; ??= 1, if ? ?. ?? 8?+1= 4 + ?=?+1 After an additional rotation by |?1> is 1 (? ?), where is sufficiently small such that the probability of the qubit being in |?2> (|?1> ) is bigger than 0.98 if ? ? (? ?). ?= 2 ?=1 ?? ?? 8?+1 8? 2 ?=1 4, the final angle from 2+ if ??= 1 (? ?) and it is if ??=
? ?,?|? ????? ?? ??? log8( ??) ? ????? ?? ? = Exponential expected time.
??????2 = 02?|? 0 2QCCA can recognize in middle log space. ??????8 = 08?|? 0 ??????8(?) = 08?|? 1 ?
Polynomial-time ?(???????) -space sweeping PTMs (open for ?(???????)-space) Linearithmic-time ?(????)-space 1PTMs Middle ?(????)-space 2QCCAs (open for better space bounds and/or polynomial-time; open for PCAs)
(1)-space 2PCAs (open for ?(1)-space (or equivalently 2PFAs) Polynomial-time ?(?)-space 2PCAs (open for polynomial-time ?(?)-space) Restarting rtQCFAs (open for polynomial-time)
