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.
|
