Paper Info
Title
Transductions computed by PC-systems of monotone deterministic restarting automata
Abstract
We associate a transduction (that is, a binary relation) with the characteristic language of a restarting automaton, and we prove that in this way monotone deterministic restarting automata yield a characterization of pushdown transductions. Then we study the class of transductions that are computed by parallel communicating systems (PC-systems) of monotone deterministic restarting automata. We will see that this class includes all transductions that are computable.
Year
DOI
Venue
2010
10.1007/978-3-642-18098-9_18
CIAA
Keywords
Field
DocType
restarting automaton,characteristic language,pushdown transductions,monotone deterministic,binary relation,communication system
Discrete mathematics,Combinatorics,Binary relation,Automaton,Mathematics,Monotone polygon
Conference
Volume
ISSN
Citations 
6482
0302-9743
3
PageRank 
References 
Authors
0.42
7
3
Name
Order
Citations
PageRank
Norbert Hundeshagen1214.86
Friedrich Otto224735.87
Marcel Vollweiler371.56