Boosting Reversible Pushdown Machines by Preprocessing
| Autor: | Andreas Malcher, Holger Bock Axelsen, Martin Kutrib, Matthias Wendlandt |
|---|---|
| Rok vydání: | 2016 |
| Předmět: |
TheoryofComputation_COMPUTATIONBYABSTRACTDEVICES
Boosting (machine learning) Finite-state machine Theoretical computer science Computer science Pushdown automaton Computer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing) 0102 computer and information sciences 02 engineering and technology 01 natural sciences Injective function TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES Deterministic finite automaton Regular language 010201 computation theory & mathematics 0202 electrical engineering electronic engineering information engineering Preprocessor 020201 artificial intelligence & image processing Computer Science::Formal Languages and Automata Theory |
| Zdroj: | Reversible Computation ISBN: 9783319405773 RC |
| Popis: | It is well known that reversible finite automata do not accept all regular languages and that reversible pushdown automata do not accept all deterministic context-free languages. It is of significant interest both from a practical and theoretical point of view to close these gaps. We here extend these reversible models by a preprocessing unit which is basically a reversible injective and length-preserving sequential transducer. It turns out that preprocessing the input using such weak devices increases the computational power of reversible deterministic finite automata to the acceptance of all regular languages, whereas for reversible pushdown automata the accepted family of languages lies strictly in between the reversible deterministic context-free languages and the real-time deterministic context-free languages. Moreover, it is shown that the computational power of both types of machines is not changed by allowing the preprocessing sequential transducer to work irreversibly. Finally, we examine the closure properties of the family of languages accepted by such machines. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|