Ahmet Celal Cem Say
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Ahmet Celal Cem Say has a total of 25 co-authors. Here are the top co-authors by number of shared publications:
- Abuzer Yakaryılmaz
Center for Quantum Computer Science University of Latvia Street LV-1586 Rīga Latvia
18 shared publications - Özlem Salehi
Institute of Theoretical and Applied Informatics, Polish Academy of Sciences, Gliwice, Poland
7 shared publications - Flavio D'Alessandro
Department of Mathematics Sapienza University of Rome 00185 Rome Italy
5 shared publications - Gökalp Demirci
Department of Computer Science University of Chicago 60637 Chicago IL USA
3 shared publications - Mehmet Utkan Gezer
Boğaziçi University
3 shared publications - Rūsiņš Freivalds
University of Latvia
3 shared publications
Latest Publications
- 31 January 2026
- Published by Springer Nature
- p. 88-99
Short and Useful Quantum Proofs for Sublogarithmic-Space Verifiers
- 31 January 2026
- Published by Springer Nature
- p. 88-99
Short and Useful Quantum Proofs for Sublogarithmic-Space Verifiers
- 20 November 2025
- Published by Elsevier in Theoretical Computer Science
- Vol. 1061
Time hierarchies for sublogarithmic-space quantum computation
- 20 November 2025
- Published by Elsevier in Theoretical Computer Science
- Vol. 1061
Time hierarchies for sublogarithmic-space quantum computation
- 28 May 2022
- Published by Springer Nature
- p. 212-224
Real-Time, Constant-Space, Constant-Randomness Verifiers
- 28 May 2022
- Published by Springer Nature
- p. 212-224
Real-Time, Constant-Space, Constant-Randomness Verifiers
- 18 February 2022
- Published by Elsevier in Information and Computation
- Vol. 288, 104878
Advice hierarchies among finite automata
- 18 February 2022
- Published by Elsevier in Information and Computation
- Vol. 288, 104878
Advice hierarchies among finite automata
- 24 March 2021
- Published by Elsevier in Information and Computation
- Vol. 288, 104744
Constant-space, constant-randomness verifiers with arbitrarily small error
- 24 March 2021
- Published by Elsevier in Information and Computation
- Vol. 288, 104744
Constant-space, constant-randomness verifiers with arbitrarily small error
- Open Access
Constant-Space, Constant-Randomness Verifiers with Arbitrarily Small Error
We study the capabilities of probabilistic finite-state machines that act as verifiers for certificates of language membership for input strings, in the regime where the verifiers are restricted to toss some fixed nonzero number of coins regardless of the input size. Say and Yakary{\i}lmaz showed that the class of languages that could be verified by these machines within an error bound strictly less than $1/2$ is precisely NL, but their construction yields verifiers with error bounds that are very close to $1/2$ for most languages in that class when the definition of "error" is strengthened to include looping forever without giving a response. We characterize a subset of NL for which verification with arbitrarily low error is possible by these extremely weak machines. It turns out that, for any $\varepsilon>0$, one can construct a constant-coin, constant-space verifier operating within error $\varepsilon$ for every language that is recognizable by a linear-time multi-head nondeterministic finite automaton (2nfa($k$)). We discuss why it is difficult to generalize this method to all of NL, and give a reasonably tight way to relate the power of linear-time 2nfa($k$)'s to simultaneous time-space complexity classes defined in terms of Turing machines.Open AccessConstant-Space, Constant-Randomness Verifiers with Arbitrarily Small Error
We study the capabilities of probabilistic finite-state machines that act as verifiers for certificates of language membership for input strings, in the regime where the verifiers are restricted to toss some fixed nonzero number of coins regardless of the input size. Say and Yakary{\i}lmaz showed that the class of languages that could be verified by these machines within an error bound strictly less than $1/2$ is precisely NL, but their construction yields verifiers with error bounds that are very close to $1/2$ for most languages in that class when the definition of "error" is strengthened to include looping forever without giving a response. We characterize a subset of NL for which verification with arbitrarily low error is possible by these extremely weak machines. It turns out that, for any $\varepsilon>0$, one can construct a constant-coin, constant-space verifier operating within error $\varepsilon$ for every language that is recognizable by a linear-time multi-head nondeterministic finite automaton (2nfa($k$)). We discuss why it is difficult to generalize this method to all of NL, and give a reasonably tight way to relate the power of linear-time 2nfa($k$)'s to simultaneous time-space complexity classes defined in terms of Turing machines. - Open Access
- 28 August 2019
- Published by Centre pour la Communication Scientifique Directe (CCSD) in Logical Methods in Computer Science
- Vol. ume 15, Is
Alternating, private alternating, and quantum alternating realtime automata
We present new results on realtime alternating, private alternating, and quantum alternating automaton models. Firstly, we show that the emptiness problem for alternating one-counter automata on unary alphabets is undecidable. Then, we present two equivalent definitions of realtime private alternating finite automata (PAFAs). We show that the emptiness problem is undecidable for PAFAs. Furthermore, PAFAs can recognize some nonregular unary languages, including the unary squares language, which seems to be difficult even for some classical counter automata with two-way input. Regarding quantum finite automata (QFAs), we show that the emptiness problem is undecidable both for universal QFAs on general alphabets, and for alternating QFAs with two alternations on unary alphabets. On the other hand, the same problem is decidable for nondeterministic QFAs on general alphabets. We also show that the unary squares language is recognized by alternating QFAs with two alternations.
- 28 August 2019
- Published by Centre pour la Communication Scientifique Directe (CCSD) in Logical Methods in Computer Science
- Vol. ume 15, Is
Open AccessAlternating, private alternating, and quantum alternating realtime automata
We present new results on realtime alternating, private alternating, and quantum alternating automaton models. Firstly, we show that the emptiness problem for alternating one-counter automata on unary alphabets is undecidable. Then, we present two equivalent definitions of realtime private alternating finite automata (PAFAs). We show that the emptiness problem is undecidable for PAFAs. Furthermore, PAFAs can recognize some nonregular unary languages, including the unary squares language, which seems to be difficult even for some classical counter automata with two-way input. Regarding quantum finite automata (QFAs), we show that the emptiness problem is undecidable both for universal QFAs on general alphabets, and for alternating QFAs with two alternations on unary alphabets. On the other hand, the same problem is decidable for nondeterministic QFAs on general alphabets. We also show that the unary squares language is recognized by alternating QFAs with two alternations.
- Open Access
Language Classes Associated With Automata Over Matrix Groups
We investigate the language classes recognized by group automata over matrix groups. For the case of $2 \times 2 $ matrices, we prove that the corresponding group automata for rational matrix groups are more powerful than the corresponding group automata for integer matrix groups. Finite automata over some special matrix groups, such as the discrete Heisenberg group and the Baumslag-Solitar group are also examined. We also introduce the notion of time complexity for group automata and demonstrate some separations among related classes. The case of linear-time bounds is examined in detail throughout our repertory of matrix group automata.Open AccessLanguage Classes Associated With Automata Over Matrix Groups
We investigate the language classes recognized by group automata over matrix groups. For the case of $2 \times 2 $ matrices, we prove that the corresponding group automata for rational matrix groups are more powerful than the corresponding group automata for integer matrix groups. Finite automata over some special matrix groups, such as the discrete Heisenberg group and the Baumslag-Solitar group are also examined. We also introduce the notion of time complexity for group automata and demonstrate some separations among related classes. The case of linear-time bounds is examined in detail throughout our repertory of matrix group automata.