Note on the Succinctness of Deterministic, Nondeterministic, Probabilistic and Quantum Finite Automata
RAIRO-Theor. Inf. Appl., 35 5 (2001) 477-490
Published online: 2002-08-15
Articles citing this article
The Citing articles tool gives a list of articles citing the current article.
The citing articles come from EDP Sciences database, as well as other publishers participating in CrossRef Cited-by Linking Program. You can set up your personal account to receive an email alert each time this article is cited by a new article (see the menu on the right-hand side of the abstract page).
Cited article:
This article has been cited by the following article(s):
Probabilistic input-driven pushdown automata
Alex Rose and Alexander OkhotinInformation and Computation 305 105312 (2025)
https://doi.org/10.1016/j.ic.2025.105312
State complexity of one-way quantum finite automata together with classical states
Ligang Xiao and Daowen QiuJournal of Computer and System Sciences 154 103659 (2025)
https://doi.org/10.1016/j.jcss.2025.103659
Latvian Quantum Finite State Automata for Unary Languages
Carlo Mereghetti, Beatrice Palano and Priscilla RaucciInternational Journal of Foundations of Computer Science 36 (03) 419 (2025)
https://doi.org/10.1142/S0129054124430032
Iterated uniform finite-state transducers on unary languages
Martin Kutrib, Andreas Malcher, Carlo Mereghetti and Beatrice PalanoTheoretical Computer Science 969 114049 (2023)
https://doi.org/10.1016/j.tcs.2023.114049
Descriptional complexity of iterated uniform finite-state transducers
Martin Kutrib, Andreas Malcher, Carlo Mereghetti and Beatrice PalanoInformation and Computation 284 104691 (2022)
https://doi.org/10.1016/j.ic.2021.104691
Guest Column
Carlo Mereghetti and Beatrice PalanoACM SIGACT News 52 (3) 38 (2021)
https://doi.org/10.1145/3494656.3494666
SOFSEM 2021: Theory and Practice of Computer Science
Martin Kutrib, Andreas Malcher, Carlo Mereghetti and Beatrice PalanoLecture Notes in Computer Science, SOFSEM 2021: Theory and Practice of Computer Science 12607 218 (2021)
https://doi.org/10.1007/978-3-030-67731-2_16
An Enhanced Photonic Quantum Finite Automaton
Alessandro Candeloro, Carlo Mereghetti, Beatrice Palano, Simone Cialdi, Matteo G. A. Paris and Stefano OlivaresApplied Sciences 11 (18) 8768 (2021)
https://doi.org/10.3390/app11188768
12442 117 (2020)
https://doi.org/10.1007/978-3-030-62536-8_10
Photonic realization of a quantum finite automaton
Carlo Mereghetti, Beatrice Palano, Simone Cialdi, et al.Physical Review Research 2 (1) (2020)
https://doi.org/10.1103/PhysRevResearch.2.013089
A Quantum Finite Automata Approach to Modeling the Chemical Reactions
Amandeep Singh Bhatia and Shenggen ZhengFrontiers in Physics 8 (2020)
https://doi.org/10.3389/fphy.2020.547370
Unary probabilistic and quantum automata on promise problems
Aida Gainutdinova and Abuzer YakaryılmazQuantum Information Processing 17 (2) (2018)
https://doi.org/10.1007/s11128-017-1799-0
Quantum finite automata: Advances on Bertoni's ideas
Maria Paola Bianchi, Carlo Mereghetti and Beatrice PalanoTheoretical Computer Science 664 39 (2017)
https://doi.org/10.1016/j.tcs.2016.01.045
Descriptional Complexity of Formal Systems
Marcos Villagra and Tomoyuki YamakamiLecture Notes in Computer Science, Descriptional Complexity of Formal Systems 9118 280 (2015)
https://doi.org/10.1007/978-3-319-19225-3_24
Developments in Language Theory
Aida Gainutdinova and Abuzer YakaryılmazLecture Notes in Computer Science, Developments in Language Theory 9168 252 (2015)
https://doi.org/10.1007/978-3-319-21500-6_20
Computing with New Resources
Shenggen Zheng and Daowen QiuLecture Notes in Computer Science, Computing with New Resources 8808 231 (2014)
https://doi.org/10.1007/978-3-319-13350-8_18
Computing with New Resources
Maria Paola Bianchi, Carlo Mereghetti and Beatrice PalanoLecture Notes in Computer Science, Computing with New Resources 8808 161 (2014)
https://doi.org/10.1007/978-3-319-13350-8_12
Removing nondeterminism in constant height pushdown automata
Zuzana Bednárová, Viliam Geffert, Carlo Mereghetti and Beatrice PalanoInformation and Computation 237 257 (2014)
https://doi.org/10.1016/j.ic.2014.03.002
Language and Automata Theory and Applications
Shenggen Zheng, Jozef Gruska and Daowen QiuLecture Notes in Computer Science, Language and Automata Theory and Applications 8370 601 (2014)
https://doi.org/10.1007/978-3-319-04921-2_49
Languages Alive
Shenggen Zheng, Daowen Qiu, Lvzhou Li and Jozef GruskaLecture Notes in Computer Science, Languages Alive 7300 273 (2012)
https://doi.org/10.1007/978-3-642-31644-9_19
Quantum automata for some multiperiodic languages
Carlo Mereghetti and Beatrice PalanoTheoretical Computer Science 387 (2) 177 (2007)
https://doi.org/10.1016/j.tcs.2007.07.037
Quantum finite automata with control language
Carlo Mereghetti and Beatrice PalanoRAIRO - Theoretical Informatics and Applications 40 (2) 315 (2006)
https://doi.org/10.1051/ita:2006007
Small size quantum automata recognizing some regular languages
Alberto Bertoni, Carlo Mereghetti and Beatrice PalanoTheoretical Computer Science 340 (2) 394 (2005)
https://doi.org/10.1016/j.tcs.2005.03.032
GOLOMB RULERS AND DIFFERENCE SETS FOR SUCCINCT QUANTUM AUTOMATA
ALBERTO BERTONI, CARLO MEREGHETTI and BEATRICE PALANOInternational Journal of Foundations of Computer Science 14 (05) 871 (2003)
https://doi.org/10.1142/S0129054103002060
Mathematical Foundations of Computer Science 2003
Gregor GramlichLecture Notes in Computer Science, Mathematical Foundations of Computer Science 2003 2747 460 (2003)
https://doi.org/10.1007/978-3-540-45138-9_40
On the Size of One-way Quantum Finite Automata with Periodic Behaviors
Carlo Mereghetti and Beatrice PalanoRAIRO - Theoretical Informatics and Applications 36 (3) 277 (2002)
https://doi.org/10.1051/ita:2002014
Theoretical Computer Science
Carlo Mereghetti and Beatrice PalanoLecture Notes in Computer Science, Theoretical Computer Science 2202 123 (2001)
https://doi.org/10.1007/3-540-45446-2_8