Další formáty:
BibTeX
LaTeX
RIS
@inproceedings{1122875, author = {Kunc, Michal and Okhotin, Alexander}, address = {Berlin}, booktitle = {Mathematical Foundations of Computer Science 2013}, doi = {http://dx.doi.org/10.1007/978-3-642-40313-2_53}, editor = {Krishnendu Chatterjee, Jirí Sgall}, keywords = {graph-walking automaton; reversible computation}, howpublished = {tištěná verze "print"}, language = {eng}, location = {Berlin}, isbn = {978-3-642-40312-5}, pages = {595-606}, publisher = {Springer}, title = {Reversibility of computations in graph-walking automata}, url = {http://dx.doi.org/10.1007/978-3-642-40313-2_53}, year = {2013} }
TY - JOUR ID - 1122875 AU - Kunc, Michal - Okhotin, Alexander PY - 2013 TI - Reversibility of computations in graph-walking automata PB - Springer CY - Berlin SN - 9783642403125 KW - graph-walking automaton KW - reversible computation UR - http://dx.doi.org/10.1007/978-3-642-40313-2_53 L2 - http://dx.doi.org/10.1007/978-3-642-40313-2_53 N2 - The paper proposes a general notation for deterministic automata traversing finite undirected structures: the graph-walking automata. This abstract notion covers such models as two-way finite automata, including their multi-tape and multi-head variants, tree-walking automata and their extension with pebbles, picture-walking automata, space-bounded Turing machines, etc. It is then demonstrated that every graph-walking automaton can be transformed to an equivalent reversible graph-walking automaton, so that every step of its computation is logically reversible. This is done with a linear blow-up in the number of states, where the linear factor depends on the degree of graphs being traversed. The construction directly applies to all basic models covered by this abstract notion. ER -
KUNC, Michal a Alexander OKHOTIN. Reversibility of computations in graph-walking automata. In Krishnendu Chatterjee, Jirí Sgall. \textit{Mathematical Foundations of Computer Science 2013}. Berlin: Springer, 2013, s.~595-606. ISBN~978-3-642-40312-5. Dostupné z: https://dx.doi.org/10.1007/978-3-642-40313-2\_{}53.
|