Paper Info
Title
Reversible and Irreversible Computations of Deterministic Finite-State Devices
Abstract
Finite-state devices with a read-only input tape that may be equipped with further resources as queues or pushdown stores are considered towards their ability to perform reversible computations. Some aspects of the notion of logical reversibility are addressed. We present some selected results on the decidability, uniqueness, and size of minimal reversible deterministic finite automata. The relations and properties of reversible automata that are equipped with storages are discussed, where we exemplarily stick with the storage types queue and pushdown store. In particular, the computational capacities, decidability problems, and closure properties are the main topics covered, and we draw attention to the overall picture and some of the main ideas involved.
Year
DOI
Venue
2015
10.1007/978-3-662-48057-1_3
Lecture Notes in Computer Science
Keywords
Field
DocType
Reversibility,Finite state devices,Minimality,Queue and pushdown storage,Decidability,Closure properties
Uniqueness,Discrete mathematics,Combinatorics,Computer science,Deterministic finite automaton,Queue,Automaton,Decidability,Finite state,Computation
Conference
Volume
ISSN
Citations 
9234
0302-9743
2
PageRank 
References 
Authors
0.50
24
1
Name
Order
Citations
PageRank
Martin Kutrib177889.77