Pith. sign in

REVIEW 4 major objections 8 minor 39 references

Reviewed by Pith at T0; open to challenge.

T0 means a machine referee read the full paper against a public rubric. The mark states how deep the mechanical check went, never who wrote it. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · glm-5.2

Quantum search cuts resetting-sequence finding from exponential to square-root

2026-07-09 01:23 UTC pith:XKOV3D5B

load-bearing objection First quantum circuit construction for FA reset sequences; core idea sound but complexity analysis incomplete the 4 major comments →

arxiv 2607.06953 v1 pith:XKOV3D5B submitted 2026-07-08 quant-ph cs.ET

A quantum model for synchronizing finite state transition systems

Martin Lukac , Khaled El-Fakih , Uraz Turker This is my paper
classification quant-ph cs.ET
keywords resetting sequencesynchronizing sequencefinite automatonquantum searchGrover's algorithmamplitude amplificationpermutative unitarytransition system
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proposes a quantum algorithm for finding resetting sequences — input sequences that drive a finite automaton to a single state regardless of where it started. The classical brute-force approach tries all k^l input sequences of length l and checks whether each one collapses all n states to the same target, costing O(k^l) time. The authors encode the automaton's transition function as a permutative unitary operator Delta, constructed by adding ancilla qubits to make irreversible transitions reversible. They then apply Delta iteratively in superposition over all k^l input sequences and all n initial states simultaneously, producing a quantum state where each input sequence is paired with the collection of final states it reaches from every starting state. Because the construction naturally groups input sequences that yield identical state-collections, a Grover search over the resulting state can find a collection where all n final states are identical — which means the corresponding input sequence is a resetting sequence. The search requires O(sqrt(k^l)) iterations instead of O(k^l), giving a quadratic speedup over brute force. The authors demonstrate the method on small simulated finite automata using a quantum simulator.

Core claim

The central mechanism is the permutative unitary operator Delta, which encodes a finite automaton's transition function into a reversible quantum operation. By applying Delta in superposition across all input sequences of length l and all n initial states, the algorithm produces a quantum state where identical state-collections naturally combine, enabling Grover's amplitude amplification to locate a resetting sequence in O(sqrt(k^l)) steps. The key insight is that the superposition-over-all-inputs-and-all-states construction factors the output space into at most n^n distinct state-collections (rather than k^l individual sequences), and that a Grover oracle checking whether all elements of a

What carries the argument

Permutative unitary operator Delta (encoding FA transitions as reversible quantum gates via ancilla registers), superposition over all input sequences and all initial states, Grover amplitude amplification targeting state-collections where all reached states are identical (Eq. 28).

Load-bearing premise

The paper assumes that the permutative unitary operator Delta can be constructed and applied efficiently for arbitrary finite automata, and that the resulting quantum circuit's qubit and gate overhead remains practical. The construction requires O(n*l*mu) ancilla qubits and does not analyze the gate complexity of the Grover oracle that checks whether all reached states are identical.

What would settle it

If the gate complexity of the Grover oracle (checking Eq. 28) or the cost of implementing Delta grows superpolynomially in n or l, the quadratic speedup over brute force would not translate into a practical advantage for realistic automaton sizes.

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

  • For partial automata, where the shortest resetting sequence can be exponential in length and checking existence is PSPACE-complete, this approach offers a concrete quadratic speedup over the only general-purpose classical method (brute-force search).
  • The method could be adapted to find other types of testing sequences used in conformance testing of reactive systems, as the authors note, since the superposition-and-search structure is not specific to resetting sequences.
  • The factoring of k^l input sequences into at most n^n distinct state-collections means that for small automata with large input alphabets, the effective search space may be much smaller than k^l, potentially offering more than just a quadratic gain in those regimes.
  • The construction provides a template for encoding any deterministic transition system as a quantum circuit, which could be reused for other automata-theoretic problems such as distinguishing sequence generation or state equivalence checking.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The practical value of the quadratic speedup depends heavily on the gate cost of implementing the Grover oracle (checking Eq. 28: that all n state registers hold the same value). For n states, this oracle requires O(n * nu) comparison gates per iteration, and the paper does not bound this cost — if it grows with n, the speedup could erode for automata with many states.
  • The space overhead of O(n * l * mu + n * nu + l * kappa) qubits could be substantial: for a partial automaton where the shortest resetting sequence length l is Theta(n^2 * 4^(n/3)), the qubit count itself becomes exponential in n, which would make the circuit impractical even before considering gate depth.
  • The claim of a quadratic speedup is relative to brute-force search only. For complete automata, Eppstein's polynomial-time algorithm already finds resetting sequences, so the quantum approach would not be competitive in that restricted class — its value is specifically for the general (partial) FA case where no polynomial classical algorithm is known.
  • The amplitude amplification step assumes a known number of solutions M'. The paper proposes using quantum counting to estimate M', but quantum counting itself has overhead and error bounds that are not analyzed — for very rare solutions, the combined counting-plus-search procedure may behave differently from ideal Grover.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

4 major / 8 minor

Summary. The paper proposes a quantum algorithm for finding resetting sequences (RS) of finite automata (FA). The approach encodes an FA's transition function as a permutative unitary operator Δ (using ancilla registers to make non-permutative transition matrices reversible), applies Δ^l in superposition over all input sequences of length l and all n initial states, and then uses Grover amplitude amplification to search for collections of reached states where all n states are identical (Eq. 28), indicating a resetting sequence. The central claim is a quadratic speedup over classical brute-force search, which is the only general method applicable to arbitrary FAs. A working example with a 3-state FA is developed throughout, and an online simulator is mentioned as proof of concept.

Significance. The problem of finding resetting sequences is well-motivated and computationally hard (NP-hard for complete FAs, PSPACE-complete for partial FAs). Applying quantum search to this problem is a natural and previously unexplored direction, and the encoding of FA transition functions as permutative unitaries via ancilla embedding is a reasonable construction. The paper provides a detailed worked example (Table 1, Eqs. 6–25) that illustrates the full pipeline from transition table to Grover measurement. The approach is falsifiable: for a given FA, one can construct the circuit and check whether measurement yields a valid RS.

major comments (4)
  1. §4, Complexity analysis: The paper claims a quadratic speedup (O(√(k^l)) vs O(k^l)) but does not account for the per-iteration cost of the Grover diffusion operator. The initial state |Q̄_n⟩_l is prepared by applying Δ^l to a product state (Eq. 20); the reflection about this state requires applying (Δ^l)^{-1}, reflecting about |0...0⟩, and reapplying Δ^l. Each Grover iteration therefore costs 2·cost(Δ^l) + cost(oracle), not just cost(oracle). The paper states the simulation cost is O(l) (§4, point 2) and the Grover cost is √(k^l) iterations (§4, point 4), but never bounds cost(Δ^l) or cost(oracle) in gate complexity. Without this, the total quantum gate complexity is unbounded and the quadratic-speedup claim is incomplete. The polynomial overhead (in n, l, k, μ) likely does not dominate √(k^l) for large l, but this analysis must be presented explicitly.
  2. §3.6, Eq. 28: The Grover oracle that checks whether all n reached states are identical (|S^p⟩_{l,c} = |S^{p+1⟩}_{l,c} for p=0..n-2) is described conceptually but its quantum circuit and gate complexity are not specified. This oracle is load-bearing for the complexity claim. The paper should describe the oracle circuit (e.g., using n-1 controlled equality checks on ν-qubit registers with ancilla flags) and bound its gate count.
  3. §3.6, Eq. 27 (Box B): The paper claims that input sequences reaching the same collection of states 'combine' or 'factor' together. However, different input sequences generally produce different garbage qubits (|G⟩^c ≠ |G⟩^d), so the corresponding basis states remain distinct in the superposition. The grouping in Eq. 27 is notational, not a quantum mechanical combination of amplitudes. This affects the M/M' analysis: M' is the number of input sequences that are resetting sequences (not the number of distinct collections), and the paper should clarify this to avoid misestimating the Grover iteration count.
  4. The abstract and conclusion state that simulation results are provided 'as a proof of concept,' but no experimental results section appears in the manuscript. The worked example (Eqs. 24–29) is illustrative but does not constitute validation on a quantum simulator. If simulation results exist, they should be reported with details (FA sizes, sequence lengths, success probabilities, number of Grover iterations); if not, the claim should be softened.
minor comments (8)
  1. §3.5: The text states 'The example FA has two states' but Table 1 defines a 3-state FA (s0, s1, s2). This should be corrected.
  2. §3.2, Eq. 10: The result shows |X_1⟩|A_0⟩_1|S_1⟩_1 = |X_1⟩|G⟩|S_2⟩, but the text below says '|G⟩_1|S⟩_1 = |0⟩|S_1⟩ = |0⟩|1⟩' when applying x_2 from s_0. The subscripts and superscripts on garbage/state registers are inconsistent and sometimes confusing; a consistent indexing scheme would help.
  3. §3.2: The notation uses both |S_0⟩, |S_1⟩, ... and |0⟩, |1⟩, |2⟩ for states interchangeably. Using one convention consistently would improve readability.
  4. §4, point 3: The SWAP gate count formula 'C = 2l²μ' is introduced without clear derivation. The expression '2((k-1)κ) + 2j(lμ+ν)' mixes k (number of inputs) and j (state index) in a way that is hard to follow. This should be clarified.
  5. §3.6: The paper mentions using Quantum Counting [5] to find M' before applying Grover, but does not discuss the cost or error bounds of the quantum counting step, which itself requires O(√(M/M')) oracle calls.
  6. Figures 1–7 are referenced but some labels (e.g., |Q⟩, |Q̄⟩, |Q̄_n⟩) are small and hard to read. The circuit diagrams would benefit from clearer annotation of register widths.
  7. The abstract contains a typo: 'starting form an initial FA state' should be 'starting from an initial FA state.'
  8. §1: 'Epsstein' should be 'Eppstein'; 'Aemerican' should be 'American' (author affiliation).

Simulated Author's Rebuttal

4 responses · 0 unresolved

We thank the referee for a careful and constructive report. All four major comments identify legitimate gaps in the manuscript that we will address in revision. Specifically: (1) we will add an explicit gate-complexity bound for cost(Δ^l) and the Grover diffusion operator, showing the per-iteration overhead is polynomial in n, l, k, μ and does not negate the quadratic speedup over O(k^l) brute-force search; (2) we will specify the equality-check oracle circuit and its gate count; (3) we will correct the M/M' analysis to clarify that M' counts resetting input sequences (not distinct collections), and that the grouping in Eq. 27 is notational; (4) we will either include a simulation results section with concrete data or soften the 'proof of concept' claim to match what is actually reported.

read point-by-point responses

  1. Referee: §4 Complexity analysis: per-iteration cost of Grover diffusion (cost of Δ^l) not bounded; quadratic speedup claim incomplete without explicit gate complexity.

    Authors: The referee is correct that the manuscript does not explicitly bound cost(Δ^l) or cost(oracle) in gate complexity, and that each Grover iteration requires applying (Δ^l), reflecting about |0...0⟩, and reapplying Δ^l, for a per-iteration cost of 2·cost(Δ^l) + cost(oracle). We will add this analysis in revision. Concretely: each application of Δ is a permutative unitary acting on κ + μ + ν qubits, implementable as a circuit of O(2^(κ+μ+ν)) elementary gates via standard reversible synthesis (e.g., the method of Soeken et al. [33] cited in the manuscript). Applying Δ sequentially l times gives cost(Δ^l) = O(l · 2^(κ+μ+ν)). Since κ = log₂k, μ = log₂m, ν = log₂n, this is O(l · k · m · n), which is polynomial in n, l, k, μ. The oracle cost (addressed in the next comment) is also polynomial. The total quantum gate complexity is therefore O(√(k^l) · [l · k · m · n + cost(oracle)]), which is O(√(k^l) · poly(n, l, k, μ)). For large l, the exponential term √(k^l) dominates, preserving the quadratic speedup over the O(k^l) classical brute-force search. We agree this must be stated explicitly and will add a dedicated complexity subsection. revision: yes

  2. Referee: §3.6, Eq. 28: Grover oracle for checking all n reached states are identical is described conceptually but circuit and gate complexity not specified.

    Authors: We agree the oracle circuit should be specified. The oracle checks |S^p⟩_{l,c} = |S^{p+1}⟩_{l,c} for p = 0,...,n-2, where each |S^p⟩ is encoded on ν qubits. The circuit consists of n-1 equality comparators, each comparing two ν-qubit registers. Each equality comparator uses ν controlled-XOR gates (to compute bitwise equality into an ancilla) followed by a multi-controlled Toffoli on ν ancilla flags, then uncomputation. One equality comparator costs O(ν) gates; the full oracle uses O(n·ν) gates plus O(n·ν) ancilla qubits for intermediate flags, with a final AND-reduction over n-1 comparator outputs costing O(n) additional gates. Total oracle cost: O(n·ν) = O(n·log₂n) gates per invocation. We will add this circuit description and gate bound to §3.6. revision: yes

  3. Referee: §3.6, Eq. 27 (Box B): grouping is notational, not a quantum-mechanical combination of amplitudes; M' should count resetting input sequences, not distinct collections.

    Authors: The referee is correct. Different input sequences generally produce different garbage qubits (|G⟩^c ≠ |G⟩^d), so the corresponding basis states remain distinct in the superposition. The grouping shown in Eq. 27 is notational—it organizes terms sharing the same reached-state collection for readability but does not represent amplitude combination at the quantum level. Consequently, M' in the Grover iteration count √(M/M') should be the number of input sequences that are resetting sequences (i.e., the number of marked items in the search space of k^l sequences), not the number of distinct collections. We will correct the M/M' analysis accordingly and clarify that the notational grouping in Eq. 27 does not reduce the effective search space for Grover's algorithm. The quadratic speedup claim is unaffected: Grover searches over k^l input sequences with M' marked solutions in O(√(k^l/M')) iterations, which is quadratic in the worst case M' = 1. revision: yes

  4. Referee: Abstract and conclusion claim simulation results 'as a proof of concept' but no experimental results section appears in the manuscript.

    Authors: The referee is correct that the manuscript does not contain a dedicated simulation results section. The worked example (Eqs. 24-29) is illustrative and does not constitute validation on a quantum simulator. We will address this in one of two ways depending on the status of our simulator at the time of resubmission: either (a) add a simulation results section reporting concrete data (FA sizes, sequence lengths, success probabilities, number of Grover iterations) from runs on a quantum simulator, or (b) if the simulator is not yet producing reportable results, soften the claim in the abstract and conclusion from 'we provide results of several simulated FAs on a quantum simulator' to a statement that the approach is illustrated through a worked example and that implementation on a quantum simulator is planned. In either case, the current mismatch between the claim and the manuscript content will be resolved. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation is self-contained using standard external results (Grover, quantum counting, reversible embedding).

full rationale

The paper's central claim—a quadratic speedup over classical brute-force search for resetting sequences—follows directly from applying Grover's amplitude amplification algorithm to a search space of size k^l. Grover's algorithm and quantum counting are standard, externally verified results (cited [14], [5]). The transition encoding uses reversible embedding techniques citing external work (Soeken et al. [33]). No parameters are fitted to data and then 'predicted.' No self-citation chain is load-bearing: the authors cite their own prior work [36] only in the related-work survey of classical RS algorithms, not as a premise for the quantum construction. The complexity argument in §4 counts O(sqrt(k^l)) Grover iterations, which is the standard Grover bound applied to the stated search space. The skeptic's concern about unanalyzed per-iteration diffusion cost (implementing (Delta^l)^{-1}) is a correctness/completeness gap, not circularity: the paper does not define its complexity in terms of its own outputs, nor does it smuggle an ansatz through self-citation. The derivation chain is: encode FA transitions as permutative unitary Delta (external technique), apply in superposition (standard), search with Grover (external). Each step references independent, established results. The minor self-citations in the bibliography do not form a circular dependency for the central claim. Score 2 reflects the presence of non-load-bearing self-citation and the fact that the complexity argument is incomplete (but not circular).

Axiom & Free-Parameter Ledger

1 free parameters · 4 axioms · 0 invented entities

The paper introduces no new physical entities or postulated particles. The ancilla registers are standard quantum computing constructs. The main concern is the unstated oracle complexity (axiom 3) and the unaddressed garbage qubit coherence issue (axiom 4), both of which are load-bearing for the complexity claims.

free parameters (1)
  • l (sequence length) = not fitted; chosen as input
    The RS length l is an input parameter to the algorithm. The paper does not discuss how l is determined; in practice one would iterate l=1,2,... until a solution is found, adding a logarithmic factor to the complexity.
axioms (4)
  • standard math Any Boolean function can be embedded into a reversible (permutative) circuit using sufficient ancilla qubits
    Invoked in §3.2 to justify constructing permutative Δ_x from non-permutative transition matrices. Cites [33] (Soeken et al. 2014) for the general embedding approach.
  • standard math Grover's algorithm provides a quadratic speedup for unstructured search over N items
    Invoked in §3.6 and §4.1 to claim O(√(k^l)) complexity. Standard result from [14].
  • domain assumption The Grover oracle for checking that all n reached states are identical (Eq. 28) can be implemented as a polynomial-size quantum circuit
    The paper assumes this oracle exists and can be applied but does not construct it or bound its gate complexity. This is load-bearing for the complexity claim.
  • ad hoc to paper Garbage qubits from different input sequences do not interfere with amplitude amplification
    In Eq. 27, the factoring into collections with identical state lists assumes garbage qubits can be grouped or ignored. The paper does not address whether differing garbage values across sequences reaching the same collection prevent the coherent superposition needed for Grover iterations.

pith-pipeline@v1.1.0-glm · 25818 in / 2362 out tokens · 487416 ms · 2026-07-09T01:23:31.278796+00:00 · methodology

0 comments
read the original abstract

We propose a quantum model for finding a resetting input sequence (RS) which can take a finite state transition system (FA), to particular state independent of its current state. The complexity of finding such sequences for various types of FA can be NP-Hard or even PSPACE-Complete. To this end, we represent the FA states, inputs, and transition function in quantum space. Accordingly, we propose a model to represent the execution of an input sequence of a particular length $l$ starting form an initial FA state. The model is extended considering the application in superposition of all input sequences of length $l$ to an initial state of the FA. The model is further extended considering the application of all input sequences to all initial states of the FA capturing for every input sequence the collection (ordered list) of states reached by applying the sequence to all states of the FA. The amplitude amplification algorithm is then used as it combines similar collections of reached states while preserving all input sequences that reach these collections. A Grover search for a reached collection where its elements correspond to the same FA state provides a RS for the FA. Our approach offers a quadratic gain over the exponential complexity of traditional brute-force method, which is the only method that can be applied to a general FA class. As a proof of concept we provide results of several simulated FAs on a quantum simulator.

Figures

Figures reproduced from arXiv: 2607.06953 by Khaled El-Fakih, Martin Lukac, Uraz Turker.

Figure 1
Figure 1. Figure 1: Circuit representing the application of an FA input [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Circuit representing the l− times application of ∆ to a sequence of l inputs encoded by |X l j ⟩ · · · |X 1 i ⟩ starting from an FA state encoded by S⟩. This represents the evolution, according to ∆, from QTS |Q⟩ to |Q⟩l leading to the FA state encoded by S⟩l . 5 [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Circuit representing the applications of all input sequences of length [PITH_FULL_IMAGE:figures/full_fig_p010_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Circuit corresponding to the FA built from the specifications in Table 1, superposed input qubits [PITH_FULL_IMAGE:figures/full_fig_p011_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Circuit showing how the qubits are routed to each of the ∆ operator when used as in circuit in [PITH_FULL_IMAGE:figures/full_fig_p011_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: A circuit representing the applications of all input sequences of length [PITH_FULL_IMAGE:figures/full_fig_p012_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: A circuit representing the application of all input sequences of length 2 to all states of the FA. [PITH_FULL_IMAGE:figures/full_fig_p014_7.png] view at source ↗

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

39 extracted references · 39 canonical work pages · 2 internal anchors

  1. [1]

    Lucas V. R. Alves and Patr´ ıcia N. Pena. Secure recovery procedure for manufacturing systems using synchronizing automata and supervisory control theory.IEEE Transactions on Automation Science and Engineering, 19(1):486–496, 2022

    work page 2022

  2. [2]

    Ananichev and Mikhail V

    Dimitry S. Ananichev and Mikhail V. Volkov. Synchronizing monotonic automata.Theor. Comput. Sci., 327(3):225–239, 2004

    work page 2004

  3. [3]

    Quantum supremacy using a programmable superconducting processor.Nature, 574:505–510, 2019

    Frank Arute and et al. Quantum supremacy using a programmable superconducting processor.Nature, 574:505–510, 2019

    work page 2019

  4. [4]

    K. Benson. Evolving finite state machines with embedded genetic programming for automatic target detection. InProceedings of the 2000 Congress on Evolutionary Computation, pages 1543–1549, 2000

    work page 2000

  5. [5]

    Springer Berlin Heidelberg, 1998

    Gilles Brassard, Peter HØyer, and Alain Tapp.Quantum counting, page 820–831. Springer Berlin Heidelberg, 1998

    work page 1998

  6. [6]

    A note on homogeneous experiments with finite automata English.Matematicko-fyzik´ alny ˇ casopis, 14:208–216, 1964

    J´ anˇCern` y. A note on homogeneous experiments with finite automata English.Matematicko-fyzik´ alny ˇ casopis, 14:208–216, 1964. 16

    work page 1964

  7. [7]

    On directable automata.Kybernetika, 7(4):289– 298, 1971

    J´ anˇCern` y, Alica Pirick´ a, and Blanka Rosenauerov´ a. On directable automata.Kybernetika, 7(4):289– 298, 1971

    work page 1971

  8. [8]

    T. S. Chow. Testing software design modeled by finite-state machines.IEEE Trans. Software Eng., 4(3):178–187, 1978

    work page 1978

  9. [9]

    Real-time sequence testing of an automotive electric machine control systems

    Gunwant Dhadyalla, Chek Yang, James Marco, and Paul Jennings. Real-time sequence testing of an automotive electric machine control systems. 04 2018

    work page 2018

  10. [10]

    FSM-based conformance testing methods: a survey annotated with experimental evaluation.Information and Software Technology, 52(12):1286–1297, 2010

    Rita Dorofeeva, Khaled El-Fakih, Stephane Maag, Ana R Cavalli, and Nina Yevtushenko. FSM-based conformance testing methods: a survey annotated with experimental evaluation.Information and Software Technology, 52(12):1286–1297, 2010

    work page 2010

  11. [11]

    Eppstein

    D. Eppstein. Reset sequences for monotonic automata.SIAM J. Comput., 19(3):500–510, 1990

    work page 1990

  12. [12]

    Improved upper bounds on synchronizing non- deterministic automata.Inf

    Zsolt Gazdag, Szabolcs Iv´ an, and Judit Nagy-Gy¨ orgy. Improved upper bounds on synchronizing non- deterministic automata.Inf. Process. Lett., 109(17):986–990, 2009

    work page 2009

  13. [13]

    Gusev, and Rapha¨ el M

    Bal´ azs Gerencs´ er, Vladimir V. Gusev, and Rapha¨ el M. Jungers. Primitive sets of nonnegative matrices and synchronizing automata.SIAM Journal on Matrix Analysis and Applications, 39(1):83–98, 2018

    work page 2018

  14. [14]

    Lov K. Grover. A fast quantum mechanical algorithm for database search. InProceedings of the Twenty- Eighth Annual ACM Symposium on Theory of Computing, STOC ’96, page 212–219, New York, NY, USA, 1996. ACM

    work page 1996

  15. [15]

    Generating Shortest Synchronizing Sequences using Answer Set Programming

    Canan G¨ uni¸ cen, Esra Erdem, and H¨ usn¨ u Yenig¨ un. Generating shortest synchronizing sequences using answer set programming.CoRR, abs/1312.6146, 2013

    work page internal anchor Pith review Pith/arXiv arXiv 2013

  16. [16]

    Mul- ticore and manycore parallelization of cheap synchronizing sequence heuristics.J

    Serta¸ c Karahoda, Osman Tufan Erenay, Kamer Kaya, Uraz Cengiz T¨ urker, and H¨ usn¨ u Yenig¨ un. Mul- ticore and manycore parallelization of cheap synchronizing sequence heuristics.J. Parallel Distributed Comput., 140:13–24, 2020

    work page 2020

  17. [17]

    ˇCern´ y’s conjecture and the road colouring problem, pages 525–565

    Jarkko Kari and Mikhail Volkov. ˇCern´ y’s conjecture and the road colouring problem, pages 525–565. 09 2021

    work page 2021

  18. [18]

    Kisielewicz, J

    A. Kisielewicz, J. Kowalski, and M. Szyku la. A fast algorithm finding the shortest reset words.Com- puting and Combinatorics, 7936:182–196

    work page

  19. [19]

    Kudlacik, A

    R. Kudlacik, A. Roman, and H. Wagner. Effective synchronizing algorithms.Expert Systems with Applications, 39(14):11746–11757, 2012

    work page 2012

  20. [20]

    Lee and M

    D. Lee and M. Yannakakis. Principles and methods of testing finite-state machines - a survey.Proceedings of the IEEE, 84(8):1089–1123, 1996

    work page 1996

  21. [21]

    Generating synchronizable test sequences based on finite state machine with distributed ports

    Gang Luo, Rachida Dssouli, Gregor von Bochmann, Pallapa Venkataram, and Abderrazak Ghedamsi. Generating synchronizable test sequences based on finite state machine with distributed ports. In Proceedings of the IFIP TC6/WG6.1 Sixth International Workshop on Protocol Test Systems VI, page 139–153, 1993

    work page 1993

  22. [22]

    Martyugin

    Pavel V. Martyugin. Complexity of problems concerning carefully synchronizing words for pfa and directing words for nfa. InCSR, pages 288–302, 2010

    work page 2010

  23. [23]

    Nielsen and Isaac L

    Michael A. Nielsen and Isaac L. Chuang.Quantum Computation and Quantum Information: 10th Anniversary Edition. Cambridge University Press, Cambridge, 2010

    work page 2010

  24. [24]

    Jahromi, Sukhbinder Singh, and Rom´ an Or´ us

    Siddhartha Patra, Saeed S. Jahromi, Sukhbinder Singh, and Rom´ an Or´ us. Efficient tensor network simulation of ibm’s largest quantum processors.Physical Review Research, 6(1), March 2024. 17

    work page 2024

  25. [25]

    On achieving complete testability of synchronous sequential circuits with synchronizing sequences

    Irith Pomeranz and Sudhakar M Reddy. On achieving complete testability of synchronous sequential circuits with synchronizing sequences. InProceedings., International Test Conference, pages 1007–1016. IEEE, 1995

    work page 1995

  26. [26]

    Rafiq and L

    O. Rafiq and L. Cacciari. Coordination algorithm for distributed testing.The Journal of Supercomput- ing, 24(2):203–211, 2003

    work page 2003

  27. [27]

    A sub-constant error-probability low-degree test, and a sub-constant error- probability PCP characterization of NP

    Ran Raz and Shmuel Safra. A sub-constant error-probability low-degree test, and a sub-constant error- probability PCP characterization of NP. InSTOC, pages 475–484, 1997

    work page 1997

  28. [28]

    A. Roman. New algorithms for finding short reset sequences in synchronizing automata. InInternational Enformatika Conference, IEC’05, August 26-28, 2005, Prague, Czech Republic, CDROM, pages 13–17, 2005

    work page 2005

  29. [29]

    Roman and M

    A. Roman and M. Szykula. Forward and backward synchronizing algorithms.Expert Syst. Appl., 42(24):9512–9527, 2015

    work page 2015

  30. [30]

    Ege Sara¸ c, ¨Omer Faruk Altun, Kamil Tolga Atam, Serta¸ c Karahoda, Kamer Kaya, and H¨ usn¨ u Yenig¨ un

    N. Ege Sara¸ c, ¨Omer Faruk Altun, Kamil Tolga Atam, Serta¸ c Karahoda, Kamer Kaya, and H¨ usn¨ u Yenig¨ un. Boosting expensive synchronizing heuristics.Expert Systems with Applications, 167:114203, 2021

    work page 2021

  31. [31]

    Shabana and M.V

    H. Shabana and M.V. Volkov. Careful synchronization of partial deterministic finite automata.Acta Informatica, 59:479–504, 2022

    work page 2022

  32. [32]

    Peter W. Shor. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer.SIAM Journal on Computing, 26(5):1484–1509, 1997

    work page 1997

  33. [33]

    Embedding of Large Boolean Functions for Reversible Logic

    Mathias Soeken, Robert Wille, Oliver Kesz¨ ocze, D. Michael Miller, and Rolf Drechsler. Embedding of large boolean functions for reversible logic.CoRR, abs/1408.3586, 2014

    work page internal anchor Pith review Pith/arXiv arXiv 2014

  34. [34]

    Synchronizing billion-scale automata.Informa- tion Sciences, 574:162–175, 2021

    Mustafa Kemal Ta¸ s, Kamer Kaya, and H¨ usn¨ u Yenig¨ un. Synchronizing billion-scale automata.Informa- tion Sciences, 574:162–175, 2021

    work page 2021

  35. [35]

    Exact synchronization for finite-state sources.Journal of Statistical Physics, 145:1181–1201, 2011

    Nicholas F Travers and James P Crutchfield. Exact synchronization for finite-state sources.Journal of Statistical Physics, 145:1181–1201, 2011

    work page 2011

  36. [36]

    Effective algorithms for constructing minimum cost adaptive distinguishing sequences.Information and Software Technology, 74:69–85, 2016

    Uraz Cengiz T¨ urker, Tongu¸ c¨Unl¨ uyurt, and H¨ usn¨ u Yenig¨ un. Effective algorithms for constructing minimum cost adaptive distinguishing sequences.Information and Software Technology, 74:69–85, 2016

    work page 2016

  37. [37]

    Mikhail V. Volkov. Synchronizing automata and the ˇ cerny conjecture. InLATA, pages 11–27, 2008

    work page 2008

  38. [38]

    Mikhail V. Volkov. Synchronizing automata preserving a chain of partial orders.Theor. Comput. Sci., 410(37):3513–3519, 2009

    work page 2009

  39. [39]

    Quantum computational advantage using photons.Science, 370(6523):1460–1463, 2020

    Han-Sen Zhong, Hui Wang, Yu-Hao Deng, Ming-Cheng Chen, Li-Chao Peng, Yi-Han Luo, Jian Qin, Dian Wu, Xing Ding, Yi Hu, et al. Quantum computational advantage using photons.Science, 370(6523):1460–1463, 2020. 18

    work page 2020