Restricted Turing Machines and Language Recognition
| Autor: | Giovanni Pighizzini |
|---|---|
| Rok vydání: | 2016 |
| Předmět: |
TheoryofComputation_COMPUTATIONBYABSTRACTDEVICES
Chomsky hierarchy Computer science 0102 computer and information sciences 02 engineering and technology Computer Science::Computational Complexity computer.software_genre 01 natural sciences Turing machine symbols.namesake Regular language 0202 electrical engineering electronic engineering information engineering Time complexity Discrete mathematics Finite-state machine Linear bounded automaton Programming language Model of computation Context-free language Pushdown automaton Nondeterministic algorithm TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES 010201 computation theory & mathematics symbols 020201 artificial intelligence & image processing computer Computer Science::Formal Languages and Automata Theory |
| Zdroj: | Language and Automata Theory and Applications ISBN: 9783319299990 LATA |
| DOI: | 10.1007/978-3-319-30000-9_3 |
| Popis: | In 1965 Hennie proved that one-tape deterministic Turing machines working in linear time are equivalent to finite automata, namely they characterize regular languages. This result has been improved in different directions, by obtaining optimal lower bounds for the time that one-tape deterministic and nondeterministic Turing machines need to recognize nonregular languages. On the other hand, in 1964 Kuroda showed that one-tape Turing machines that are not allowed to use any extra space, besides the part of the tape which initially contains the input, namely linear bounded automata, recognize exactly context-sensitive languages. In 1967 Hibbard proved that for each integer \(d\ge 2\), one-tape Turing machines that are allowed to rewrite each tape cell only in the first d visits are equivalent to pushdown automata. This gives a characterization of the class of context-free languages in terms of restricted Turing machines. We discuss these and other related models, by presenting an overview of some fundamental results related to them. Descriptional complexity aspects are also considered. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|