Descriptional and computational complexity of finite automata—A survey
Article Properties
-
LanguageEnglish
-
DOI (url)
-
Publication Date2011/03/01
-
Journal
-
Indian UGC (journal)
-
Refrences88
-
Citations49
-
Markus Holzer
-
Martin Kutrib
Cite
Holzer, Markus, and Martin Kutrib. “Descriptional and Computational Complexity of Finite automata—A Survey”. Information and Computation, vol. 209, no. 3, 2011, pp. 456-70, https://doi.org/10.1016/j.ic.2010.11.013.
Holzer, M., & Kutrib, M. (2011). Descriptional and computational complexity of finite automata—A survey. Information and Computation, 209(3), 456-470. https://doi.org/10.1016/j.ic.2010.11.013
Holzer M, Kutrib M. Descriptional and computational complexity of finite automata—A survey. Information and Computation. 2011;209(3):456-70.
Journal Categories
Science
Mathematics
Instruments and machines
Electronic computers
Computer science
Science
Mathematics
Instruments and machines
Electronic computers
Computer science
Computer software
Technology
Electrical engineering
Electronics
Nuclear engineering
Electronics
Computer engineering
Computer hardware
Technology
Technology (General)
Industrial engineering
Management engineering
Applied mathematics
Quantitative methods
Refrences
| Title | Journal | Journal Categories | Citations | Publication Date |
|---|---|---|---|---|
| The complexity of computing the permanent | Theoretical Computer Science |
| 1,007 | 1979 |
| A note on undecidable properties of formal languages | 1968 | |||
| On NFAs where all states are final, initial, or both | Theoretical Computer Science |
| 18 | 2009 |
| Detecting palindromes, patterns and borders in regular languages | Information and Computation |
| 7 | 2009 |
| Nondeterministic finite automata – recent results on the descriptional and computational complexity | International Journal of Foundations of Computer Science |
| 2009 |
Citations
| Title | Journal | Journal Categories | Citations | Publication Date |
|---|---|---|---|---|
| Converting finite width AFAs to nondeterministic and universal finite automata | Theoretical Computer Science |
| 2024 | |
Unary Quantum Finite State Automata with Control Language | Applied Sciences |
| 2024 | |
| On the complexity of decision problems for some classes of machines and applications | Information and Computation |
| 2023 | |
| Distributed graph problems through an automata-theoretic lens | Theoretical Computer Science |
| 2023 | |
State Complexity of Permutation and the Language Inclusion Problem up to Parikh Equivalence on Alphabetical Pattern Constraints and Partially Ordered NFAs | International Journal of Foundations of Computer Science |
| 2023 |
Citations Analysis
The category
Science: Mathematics: Instruments and machines: Electronic computers. Computer science 43
is the most commonly referenced area in studies that cite this article. The first research to cite this article was titled COMPLEXITY IN UNION-FREE REGULAR LANGUAGES and was published in 2011. The most recent citation comes from a 2024 study titled Converting finite width AFAs to nondeterministic and universal finite automata. This article reached its peak citation in 2017, with 7 citations. It has been cited in 19 different journals, 21% of which are open access. Among related journals, the Theoretical Computer Science cited this research the most, with 12 citations. The chart below illustrates the annual citation trends for this article.