Minimizing finite automata is computationally hard

Article Properties
Cite
Malcher, Andreas. “Minimizing Finite Automata Is Computationally Hard”. Theoretical Computer Science, vol. 327, no. 3, 2004, pp. 375-90, https://doi.org/10.1016/j.tcs.2004.03.070.
Malcher, A. (2004). Minimizing finite automata is computationally hard. Theoretical Computer Science, 327(3), 375-390. https://doi.org/10.1016/j.tcs.2004.03.070
Malcher, Andreas. “Minimizing Finite Automata Is Computationally Hard”. Theoretical Computer Science 327, no. 3 (2004): 375-90. https://doi.org/10.1016/j.tcs.2004.03.070.
Malcher A. Minimizing finite automata is computationally hard. Theoretical Computer Science. 2004;327(3):375-90.
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
You May Also Like
Refrences
Title Journal Journal Categories Citations Publication Date
On finite automata with limited nondeterminism Acta Informatica
  • Technology: Technology (General): Industrial engineering. Management engineering: Information technology
  • Technology: Electrical engineering. Electronics. Nuclear engineering: Telecommunication
  • Science: Science (General): Cybernetics: Information theory
  • Science: Mathematics: Instruments and machines: Electronic computers. Computer science
 9 1998
Minimal NFA Problems are Hard SIAM Journal on Computing
  • Science: Mathematics: Instruments and machines: Electronic computers. Computer science
  • Technology: Technology (General): Industrial engineering. Management engineering: Applied mathematics. Quantitative methods
  • Science: Mathematics: Instruments and machines: Electronic computers. Computer science: Computer software
  • Technology: Electrical engineering. Electronics. Nuclear engineering: Electronics: Computer engineering. Computer hardware
  • Science: Mathematics: Instruments and machines: Electronic computers. Computer science
 65 1993
On measuring nondeterminism in regular languages 1990
Amounts of nondeterminism in finite automata Acta Informatica
  • Technology: Technology (General): Industrial engineering. Management engineering: Information technology
  • Technology: Electrical engineering. Electronics. Nuclear engineering: Telecommunication
  • Science: Science (General): Cybernetics: Information theory
  • Science: Mathematics: Instruments and machines: Electronic computers. Computer science
 1980
Complexity of automaton identification from given data 1978
Refrences Analysis
Category Category Repetition
Science: Mathematics: Instruments and machines: Electronic computers. Computer science8
Technology: Electrical engineering. Electronics. Nuclear engineering: Electronics: Computer engineering. Computer hardware5
Science: Mathematics: Instruments and machines: Electronic computers. Computer science: Computer software3
Technology: Technology (General): Industrial engineering. Management engineering: Information technology2
Technology: Electrical engineering. Electronics. Nuclear engineering: Telecommunication2
Science: Science (General): Cybernetics: Information theory2
Technology: Technology (General): Industrial engineering. Management engineering: Applied mathematics. Quantitative methods1
The category Science: Mathematics: Instruments and machines: Electronic computers. Computer science 8 is the most frequently represented among the references in this article. It primarily includes studies from Journal of Computer and System Sciences and Acta Informatica. The chart below illustrates the number of referenced publications per year.
Refrences used by this article by year
Citations
Title Journal Journal Categories Citations Publication Date
Computational complexity of problems for deterministic presentations of sofic shifts Theoretical Computer Science
  • 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
  • Science: Mathematics: Instruments and machines: Electronic computers. Computer science
 2022
Computational complexity of k-block conjugacy Theoretical Computer Science
  • 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
  • Science: Mathematics: Instruments and machines: Electronic computers. Computer science
 2 2021
Approximate reduction of finite automata for high-speed network intrusion detection International Journal on Software Tools for Technology Transfer
  • Science: Mathematics: Instruments and machines: Electronic computers. Computer science: Computer software
  • Science: Mathematics: Instruments and machines: Electronic computers. Computer science: Computer software
  • Technology: Electrical engineering. Electronics. Nuclear engineering: Electronics: Computer engineering. Computer hardware
  • Science: Mathematics: Instruments and machines: Electronic computers. Computer science
 6 2019
The tractability frontier for NFA minimization Journal of Computer and System Sciences
  • Technology: Electrical engineering. Electronics. Nuclear engineering: Electronics: Computer engineering. Computer hardware
  • 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
  • Science: Mathematics: Instruments and machines: Electronic computers. Computer science
 8 2012
Descriptional and computational complexity of finite automata—A survey Information and Computation
  • Science: Mathematics: Instruments and machines: Electronic computers. Computer science
  • Technology: Technology (General): Industrial engineering. Management engineering: Applied mathematics. Quantitative methods
  • Science: Mathematics: Instruments and machines: Electronic computers. Computer science: Computer software
  • Technology: Electrical engineering. Electronics. Nuclear engineering: Electronics: Computer engineering. Computer hardware
  • Science: Mathematics: Instruments and machines: Electronic computers. Computer science
 49 2011
Citations Analysis
Category Category Repetition
Science: Mathematics: Instruments and machines: Electronic computers. Computer science9
Science: Mathematics: Instruments and machines: Electronic computers. Computer science: Computer software9
Technology: Electrical engineering. Electronics. Nuclear engineering: Electronics: Computer engineering. Computer hardware9
Technology: Technology (General): Industrial engineering. Management engineering: Applied mathematics. Quantitative methods1
The category Science: Mathematics: Instruments and machines: Electronic computers. Computer science 9 is the most commonly referenced area in studies that cite this article. The first research to cite this article was titled An approximation algorithm for state minimization in 2-MDFAs and was published in 2006. The most recent citation comes from a 2022 study titled Computational complexity of problems for deterministic presentations of sofic shifts. This article reached its peak citation in 2011, with 2 citations. It has been cited in 7 different journals. Among related journals, the Journal of Computer and System Sciences cited this research the most, with 3 citations. The chart below illustrates the annual citation trends for this article.
Citations used this article by year