Tree-walking automata cannot be determinized

Article Properties
Cite
Bojańczyk, Mikołaj, and Thomas Colcombet. “Tree-Walking Automata Cannot Be Determinized”. Theoretical Computer Science, vol. 350, no. 2-3, 2006, pp. 164-73, https://doi.org/10.1016/j.tcs.2005.10.031.
Bojańczyk, M., & Colcombet, T. (2006). Tree-walking automata cannot be determinized. Theoretical Computer Science, 350(2-3), 164-173. https://doi.org/10.1016/j.tcs.2005.10.031
Bojańczyk M, Colcombet T. Tree-walking automata cannot be determinized. Theoretical Computer Science. 2006;350(2-3):164-73.
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
Parallel two-way automata on directed ordered acyclic graphs 1981
Translations on a context-free grammar 1971
Trips on trees 1999
Tree-walking pebble automata 1999
Automata on a 2-dimensional tape 1967
Citations
Title Journal Journal Categories Citations Publication Date
Complexity of the emptiness problem for graph-walking automata and for tilings with star subgraphs 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
 2024
State complexity of transforming graph-walking automata to halting, returning and reversible 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
 2 2023
Homomorphisms and inverse homomorphisms on graph-walking automata 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
 2023
Deterministic Real-Time Tree-Walking-Storage Automata Electronic Proceedings in Theoretical Computer Science
  • Science: Mathematics: Instruments and machines: Electronic computers. Computer science
 2023
Reversibility of computations in graph-walking automata 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
 3 2020
Citations Analysis
Category Category Repetition
Science: Mathematics: Instruments and machines: Electronic computers. Computer science9
Science: Mathematics: Instruments and machines: Electronic computers. Computer science: Computer software8
Technology: Electrical engineering. Electronics. Nuclear engineering: Electronics: Computer engineering. Computer hardware8
Technology: Technology (General): Industrial engineering. Management engineering: Applied mathematics. Quantitative methods4
Science: Mathematics1
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 Tree-Walking Automata Do Not Recognize All Regular Languages and was published in 2008. The most recent citation comes from a 2024 study titled Complexity of the emptiness problem for graph-walking automata and for tilings with star subgraphs. This article reached its peak citation in 2023, with 3 citations. It has been cited in 6 different journals, 16% of which are open access. Among related journals, the Information and Computation 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