Outline  tu-logo ur-logo

Computation with Absolutely No Space Overhead

Lane Hemaspaandra^{1} Proshanto Mukherji^{1} Till Tantau^{2}

1Department of Computer Science University of Rochester

2Fakultät für Elektrotechnik und Informatik Technical University of Berlin

Developments in Language Theory Conference, 2003

Outline  tu-logo ur-logo

Outline

1 The Model of Overhead-Free Computation

The Standard Model of Linear Space Our Model of Absolutely No Space Overhead

2 The Power of Overhead-Free Computation

Palindromes Linear Languages Context-Free Languages with a Forbidden Subword Languages Complete for Polynomial Space

3 Limitations of Overhead-Free Computation

Linear Space is Strictly More Powerful

1 The Model of Overhead-Free Computation

The Standard Model of Linear Space Our Model of Absolutely No Space Overhead

2 The Power of Overhead-Free Computation

Palindromes Linear Languages Context-Free Languages with a Forbidden Subword Languages Complete for Polynomial Space

3 Limitations of Overhead-Free Computation

Linear Space is Strictly More Powerful

1 The Model of Overhead-Free Computation

The Standard Model of Linear Space Our Model of Absolutely No Space Overhead

2 The Power of Overhead-Free Computation

Palindromes Linear Languages Context-Free Languages with a Forbidden Subword Languages Complete for Polynomial Space

3 Limitations of Overhead-Free Computation

Linear Space is Strictly More Powerful

Models Power of the Model Limitations of the Model Summary  Standard Model Our Model  tu-logo ur-logo

Outline

1 The Model of Overhead-Free Computation

The Standard Model of Linear Space Our Model of Absolutely No Space Overhead

2 The Power of Overhead-Free Computation

Palindromes Linear Languages Context-Free Languages with a Forbidden Subword Languages Complete for Polynomial Space

3 Limitations of Overhead-Free Computation

Models Power of the Model Limitations of the Model Summary  Standard Model Our Model  tu-logo ur-logo

The Standard Model of Linear Space

Linear Space is Strictly More Powerful computerimage Turing machine 00100100tape Characteristics

Input fills fixed-size tape Input may be modified Tape alphabet is larger than input alphabet

Hemaspaandra, Mukherji, Tantau  Computation with Absolutely No Space Overhead  6

computerworkingimage Turing machine $0100100tape Characteristics

Input fills fixed-size tape Input may be modified Tape alphabet is larger than input alphabet

Hemaspaandra, Mukherji, Tantau  Computation with Absolutely No Space Overhead  7

computerworkingimage Turing machine $0100100tape Characteristics

Input fills fixed-size tape Input may be modified Tape alphabet is larger than input alphabet

Hemaspaandra, Mukherji, Tantau  Computation with Absolutely No Space Overhead  8

computerworkingimage Turing machine $010010$tape Characteristics

Input fills fixed-size tape Input may be modified Tape alphabet is larger than input alphabet

Hemaspaandra, Mukherji, Tantau  Computation with Absolutely No Space Overhead  9

computerworkingimage Turing machine $010010$tape Characteristics

Input fills fixed-size tape Input may be modified Tape alphabet is larger than input alphabet

Hemaspaandra, Mukherji, Tantau  Computation with Absolutely No Space Overhead  10

computerworkingimage Turing machine $$10010$tape Characteristics

Input fills fixed-size tape Input may be modified Tape alphabet is larger than input alphabet

Hemaspaandra, Mukherji, Tantau  Computation with Absolutely No Space Overhead  11

computerworkingimage Turing machine $$10010$tape Characteristics

Input fills fixed-size tape Input may be modified Tape alphabet is larger than input alphabet

Hemaspaandra, Mukherji, Tantau  Computation with Absolutely No Space Overhead  12

computerworkingimage Turing machine $$1001$$tape Characteristics

Input fills fixed-size tape Input may be modified Tape alphabet is larger than input alphabet

Hemaspaandra, Mukherji, Tantau  Computation with Absolutely No Space Overhead  13

computerworkingimage Turing machine $$$$$$$$tape Characteristics

Input fills fixed-size tape Input may be modified Tape alphabet is larger than input alphabet

Hemaspaandra, Mukherji, Tantau  Computation with Absolutely No Space Overhead  14

computerimage Turing machine $$$$$$$$tape Characteristics

Input fills fixed-size tape Input may be modified Tape alphabet is larger than input alphabet

Hemaspaandra, Mukherji, Tantau  Computation with Absolutely No Space Overhead  15

Models Power of the Model Limitations of the Model Summary  Standard Model Our Model  tu-logo ur-logo

Linear Space is a Powerful Model

CFL DLINSPACE

NLINSPACE= CSL

PSPACE

PSPACE-hard
Hemaspaandra, Mukherji, Tantau  Computation with Absolutely No Space Overhead  16

Models Power of the Model Limitations of the Model Summary  Standard Model Our Model  tu-logo ur-logo

Outline

1 The Model of Overhead-Free Computation

The Standard Model of Linear Space Our Model of Absolutely No Space Overhead

2 The Power of Overhead-Free Computation

Palindromes Linear Languages Context-Free Languages with a Forbidden Subword Languages Complete for Polynomial Space

3 Limitations of Overhead-Free Computation

Models Power of the Model Limitations of the Model Summary  Standard Model Our Model  tu-logo ur-logo

Our Model of “Absolutely No Space Overhead”

Linear Space is Strictly More Powerful apple Turing machine 00100100tape Characteristics

Input fills fixed-size tape Input may be modified Tape alphabet equals input alphabet

Hemaspaandra, Mukherji, Tantau  Computation with Absolutely No Space Overhead  18

appleworking Turing machine 10100100tape Characteristics

Input fills fixed-size tape Input may be modified Tape alphabet equals input alphabet

Hemaspaandra, Mukherji, Tantau  Computation with Absolutely No Space Overhead  19

appleworking Turing machine 10100100tape Characteristics

Input fills fixed-size tape Input may be modified Tape alphabet equals input alphabet

Hemaspaandra, Mukherji, Tantau  Computation with Absolutely No Space Overhead  20

appleworking Turing machine 10100101tape Characteristics

Input fills fixed-size tape Input may be modified Tape alphabet equals input alphabet

Hemaspaandra, Mukherji, Tantau  Computation with Absolutely No Space Overhead  21

appleworking Turing machine 10100101tape Characteristics

Input fills fixed-size tape Input may be modified Tape alphabet equals input alphabet

Hemaspaandra, Mukherji, Tantau  Computation with Absolutely No Space Overhead  22

appleworking Turing machine 11100101tape Characteristics

Input fills fixed-size tape Input may be modified Tape alphabet equals input alphabet

Hemaspaandra, Mukherji, Tantau  Computation with Absolutely No Space Overhead  23

Models Power of the Model Limitations of the Model Summary  Standard Model Our Model  tu-logo ur-logo

Our Model of “Absolutely No Space Overhead”

apple Turing machine ram Intuition

Tape is used like a RAM module.

Hemaspaandra, Mukherji, Tantau  Computation with Absolutely No Space Overhead  24

Models Power of the Model Limitations of the Model Summary  Standard Model Our Model  tu-logo ur-logo

Definition of Overhead-Free Computations

Definition A Turing machine is overhead-free if

1 it has only a single tape, 2 writes only on input cells, 3 writes only symbols drawn from the input alphabet.

Models Power of the Model Limitations of the Model Summary  Standard Model Our Model  tu-logo ur-logo

Overhead-Free Computation Complexity Classes

Definition A language L ⊆ Σ^{∗} is in

DOF if L is accepted by a deterministic overhead-free

machine with input alphabet Σ, DOF_{poly} if L is accepted by a deterministic overhead-free

machine with input alphabet Σ in polynomial time. NOF is the nondeterministic version of DOF, NOF_{poly} is the nondeterministic version of DOF_{poly}.

Definition A language L ⊆ Σ^{∗} is in

DOF if L is accepted by a deterministic overhead-free

machine with input alphabet Σ, DOF_{poly} if L is accepted by a deterministic overhead-free

machine with input alphabet Σ in polynomial time. NOF is the nondeterministic version of DOF, NOF_{poly} is the nondeterministic version of DOF_{poly}.

Definition A language L ⊆ Σ^{∗} is in

DOF if L is accepted by a deterministic overhead-free

machine with input alphabet Σ, DOF_{poly} if L is accepted by a deterministic overhead-free

machine with input alphabet Σ in polynomial time. NOF is the nondeterministic version of DOF, NOF_{poly} is the nondeterministic version of DOF_{poly}.

Definition A language L ⊆ Σ^{∗} is in

DOF if L is accepted by a deterministic overhead-free

machine with input alphabet Σ, DOF_{poly} if L is accepted by a deterministic overhead-free

machine with input alphabet Σ in polynomial time. NOF is the nondeterministic version of DOF, NOF_{poly} is the nondeterministic version of DOF_{poly}.

Models Power of the Model Limitations of the Model Summary  Standard Model Our Model  tu-logo ur-logo

Simple Relationships among Overhead-Free Computation Classes

DOF_{poly} DOF NOF_{poly} NOF NLINSPACE

Models Power of the Model Limitations of the Model Summary  Palindromes Linear Languages Forbidden Subword Complete Languages  tu-logo ur-logo

Outline

1 The Model of Overhead-Free Computation

The Standard Model of Linear Space Our Model of Absolutely No Space Overhead

2 The Power of Overhead-Free Computation

Palindromes Linear Languages Context-Free Languages with a Forbidden Subword Languages Complete for Polynomial Space

3 Limitations of Overhead-Free Computation

Models Power of the Model Limitations of the Model Summary  Palindromes Linear Languages Forbidden Subword Complete Languages  tu-logo ur-logo

Palindromes Can be Accepted in an Overhead-Free Way

Linear Space is Strictly More Powerful apple overhead-free machine 00100100tape Algorithm Phase 1: Compare first and last bit

Place left end marker Place right end marker

Phase 2: Compare bits next to end markers

Find left end marker Advance left end marker Find right end marker Advance right end marker

Hemaspaandra, Mukherji, Tantau  Computation with Absolutely No Space Overhead  32

appleworking overhead-free machine 10100100tape Algorithm Phase 1: Compare first and last bit

Place left end marker Place right end marker

Phase 2: Compare bits next to end markers

Find left end marker Advance left end marker Find right end marker Advance right end marker

Hemaspaandra, Mukherji, Tantau  Computation with Absolutely No Space Overhead  33

appleworking overhead-free machine 10100100tape Algorithm Phase 1: Compare first and last bit

Place left end marker Place right end marker

Phase 2: Compare bits next to end markers

Find left end marker Advance left end marker Find right end marker Advance right end marker

Hemaspaandra, Mukherji, Tantau  Computation with Absolutely No Space Overhead  34

appleworking overhead-free machine 10100101tape Algorithm Phase 1: Compare first and last bit

Place left end marker Place right end marker

Phase 2: Compare bits next to end markers

Find left end marker Advance left end marker Find right end marker Advance right end marker

Hemaspaandra, Mukherji, Tantau  Computation with Absolutely No Space Overhead  35

appleworking overhead-free machine 10100101tape Algorithm Phase 1: Compare first and last bit

Place left end marker Place right end marker

Phase 2: Compare bits next to end markers

Find left end marker Advance left end marker Find right end marker Advance right end marker

Hemaspaandra, Mukherji, Tantau  Computation with Absolutely No Space Overhead  36

appleworking overhead-free machine 01100101tape Algorithm Phase 1: Compare first and last bit

Place left end marker Place right end marker

Phase 2: Compare bits next to end markers

Find left end marker Advance left end marker Find right end marker Advance right end marker

Hemaspaandra, Mukherji, Tantau  Computation with Absolutely No Space Overhead  37

appleworking overhead-free machine 01100101tape Algorithm Phase 1: Compare first and last bit

Place left end marker Place right end marker

Phase 2: Compare bits next to end markers

Find left end marker Advance left end marker Find right end marker Advance right end marker

Hemaspaandra, Mukherji, Tantau  Computation with Absolutely No Space Overhead  38

appleworking overhead-free machine 01100110tape Algorithm Phase 1: Compare first and last bit

Place left end marker Place right end marker

Phase 2: Compare bits next to end markers

Find left end marker Advance left end marker Find right end marker Advance right end marker

Hemaspaandra, Mukherji, Tantau  Computation with Absolutely No Space Overhead  39

appleworking overhead-free machine 01100110tape Algorithm Phase 1: Compare first and last bit

Place left end marker Place right end marker

Phase 2: Compare bits next to end markers

Find left end marker Advance left end marker Find right end marker Advance right end marker

Hemaspaandra, Mukherji, Tantau  Computation with Absolutely No Space Overhead  40

appleworking overhead-free machine 00100110tape Algorithm Phase 1: Compare first and last bit

Place left end marker Place right end marker

Phase 2: Compare bits next to end markers

Find left end marker Advance left end marker Find right end marker Advance right end marker

Hemaspaandra, Mukherji, Tantau  Computation with Absolutely No Space Overhead  41

appleworking overhead-free machine 00100110tape Algorithm Phase 1: Compare first and last bit

Place left end marker Place right end marker

Phase 2: Compare bits next to end markers

Find left end marker Advance left end marker Find right end marker Advance right end marker

Hemaspaandra, Mukherji, Tantau  Computation with Absolutely No Space Overhead  42

appleworking overhead-free machine 00100100tape Algorithm Phase 1: Compare first and last bit

Place left end marker Place right end marker

Phase 2: Compare bits next to end markers

Find left end marker Advance left end marker Find right end marker Advance right end marker

Hemaspaandra, Mukherji, Tantau  Computation with Absolutely No Space Overhead  43

appleworking overhead-free machine 00100100tape Algorithm Phase 1: Compare first and last bit

Place left end marker Place right end marker

Phase 2: Compare bits next to end markers

Find left end marker Advance left end marker Find right end marker Advance right end marker

Hemaspaandra, Mukherji, Tantau  Computation with Absolutely No Space Overhead  44

appleworking overhead-free machine 00010100tape Algorithm Phase 1: Compare first and last bit

Place left end marker Place right end marker

Phase 2: Compare bits next to end markers

Find left end marker Advance left end marker Find right end marker Advance right end marker

Hemaspaandra, Mukherji, Tantau  Computation with Absolutely No Space Overhead  45

appleworking overhead-free machine 00010100tape Algorithm Phase 1: Compare first and last bit

Place left end marker Place right end marker

Phase 2: Compare bits next to end markers

Find left end marker Advance left end marker Find right end marker Advance right end marker

Hemaspaandra, Mukherji, Tantau  Computation with Absolutely No Space Overhead  46

apple overhead-free machine 00011000tape Algorithm Phase 1: Compare first and last bit

Place left end marker Place right end marker

Phase 2: Compare bits next to end markers

Find left end marker Advance left end marker Find right end marker Advance right end marker

Hemaspaandra, Mukherji, Tantau  Computation with Absolutely No Space Overhead  47

Models Power of the Model Limitations of the Model Summary  Palindromes Linear Languages Forbidden Subword Complete Languages  tu-logo ur-logo

Relationships among Overhead-Free Computation Classes

DOF_{poly} DOF NOF_{poly} NOF Palindromes

1 The Model of Overhead-Free Computation

The Standard Model of Linear Space Our Model of Absolutely No Space Overhead

2 The Power of Overhead-Free Computation

Palindromes Linear Languages Context-Free Languages with a Forbidden Subword Languages Complete for Polynomial Space

3 Limitations of Overhead-Free Computation

Linear Space is Strictly More Powerful

Models Power of the Model Limitations of the Model Summary  Palindromes Linear Languages Forbidden Subword Complete Languages  tu-logo ur-logo

A Review of Linear Grammars

Definition A grammar is linear if it is context-free and there is only one nonterminal per right-hand side.

Example G_{1}: S → 00S0 | 1 and G_{2}: S → 0S10 | 0.

Definition A grammar is deterministic if “there is always only one rule that can be applied.”

Example G_{1}: S → 00S0 | 1 is deterministic. G_{2}: S → 0S10 | 0 is not deterministic.

Hemaspaandra, Mukherji, Tantau  Computation with Absolutely No Space Overhead  50

Models Power of the Model Limitations of the Model Summary  Palindromes Linear Languages Forbidden Subword Complete Languages  tu-logo ur-logo

A Review of Linear Grammars

Definition A grammar is linear if it is context-free and there is only one nonterminal per right-hand side.

Example G_{1}: S → 00S0 | 1 and G_{2}: S → 0S10 | 0.

Definition A grammar is deterministic if “there is always only one rule that can be applied.”

Example G_{1}: S → 00S0 | 1 is deterministic. G_{2}: S → 0S10 | 0 is not deterministic.

Hemaspaandra, Mukherji, Tantau  Computation with Absolutely No Space Overhead  51

Models Power of the Model Limitations of the Model Summary  Palindromes Linear Languages Forbidden Subword Complete Languages  tu-logo ur-logo

Deterministic Linear Languages Can Be Accepted in an Overhead-Free Way

Theorem Every deterministic linear language is in DOF_{poly}.

Models Power of the Model Limitations of the Model Summary  Palindromes Linear Languages Forbidden Subword Complete Languages  tu-logo ur-logo

Metalinear Languages Can Be Accepted in an Overhead-Free Way

Definition A language is metalinear if it is the concatenation of linear languages.

Example triple-palindrome = {uvw | u, v, and w are palindromes }.

Theorem Every metalinear language is in NOF_{poly}.

Definition A language is metalinear if it is the concatenation of linear languages.

Example triple-palindrome = {uvw | u, v, and w are palindromes }.

Theorem Every metalinear language is in NOF_{poly}.

Definition A language is metalinear if it is the concatenation of linear languages.

Example triple-palindrome = {uvw | u, v, and w are palindromes }.

Theorem Every metalinear language is in NOF_{poly}.

DOF_{poly}

NOF_{poly}

NOF

deterministic metalinear linear

1 The Model of Overhead-Free Computation

The Standard Model of Linear Space Our Model of Absolutely No Space Overhead

2 The Power of Overhead-Free Computation

Palindromes Linear Languages Context-Free Languages with a Forbidden Subword Languages Complete for Polynomial Space

3 Limitations of Overhead-Free Computation

Models Power of the Model Limitations of the Model Summary  Palindromes Linear Languages Forbidden Subword Complete Languages  tu-logo ur-logo

Definition of Almost-Overhead-Free Computations

Linear Space is Strictly More Powerful Definition A Turing machine is almost-overhead-free if

1 it has only a single tape, 2 writes only on input cells, 3 writes only symbols drawn from the input alphabet

plus one special symbol.

Definition A Turing machine is almost-overhead-free if

1 it has only a single tape, 2 writes only on input cells, 3 writes only symbols drawn from the input alphabet

plus one special symbol.

Definition A Turing machine is almost-overhead-free if

1 it has only a single tape, 2 writes only on input cells, 3 writes only symbols drawn from the input alphabet

plus one special symbol.

Models Power of the Model Limitations of the Model Summary  Palindromes Linear Languages Forbidden Subword Complete Languages  tu-logo ur-logo

Context-Free Languages with a Forbidden Subword Can Be Accepted in an Overhead-Free Way

Theorem Let L be a context-free language with a forbidden word. Then L ∈ NOF_{poly}.

Skip proof

Models Power of the Model Limitations of the Model Summary  Palindromes Linear Languages Forbidden Subword Complete Languages  tu-logo ur-logo

Context-Free Languages with a Forbidden Subword Can Be Accepted in an Overhead-Free Way

Theorem Let L be a context-free language with a forbidden word. Then L ∈ NOF_{poly}.

Proof. Every context-free language can be accepted by a nondeterministic almost-overhead-free machine in polynomial time.

DOF_{poly}

NOF_{poly}

NOF

CFL with forbidden subwords

1 The Model of Overhead-Free Computation

The Standard Model of Linear Space Our Model of Absolutely No Space Overhead

2 The Power of Overhead-Free Computation

Palindromes Linear Languages Context-Free Languages with a Forbidden Subword Languages Complete for Polynomial Space

3 Limitations of Overhead-Free Computation

Linear Space is Strictly More Powerful

Models Power of the Model Limitations of the Model Summary  Palindromes Linear Languages Forbidden Subword Complete Languages  tu-logo ur-logo

Overhead-Free Languages can be PSPACE-Complete

Theorem DOF contains languages that are complete for PSPACE.

Proof details

Hemaspaandra, Mukherji, Tantau  Computation with Absolutely No Space Overhead  65

DOF_{poly} DOF NOF_{poly} NOF PSPACE-hard

Models Power of the Model Limitations of the Model Summary  Strict Inclusion  tu-logo ur-logo

Outline

1 The Model of Overhead-Free Computation

The Standard Model of Linear Space Our Model of Absolutely No Space Overhead

2 The Power of Overhead-Free Computation

Palindromes Linear Languages Context-Free Languages with a Forbidden Subword Languages Complete for Polynomial Space

3 Limitations of Overhead-Free Computation

Linear Space is Strictly More Powerful

Models Power of the Model Limitations of the Model Summary  Strict Inclusion  tu-logo ur-logo

Some Context-Sensitive Languages Cannot be Accepted in an Overhead-Free Way

Theorem DOF ⊊ DLINSPACE.

Theorem NOF ⊊ NLINSPACE.

The proofs are based on old diagonalisations due to Feldman, Owings, and Seiferas.

Models Power of the Model Limitations of the Model Summary  Strict Inclusion  tu-logo ur-logo

Relationships among Overhead-Free Computation Classes

DOF NOF DLINSPACE NLINSPACE PSPACE-hard

Models Power of the Model Limitations of the Model Summary  Strict Inclusion  tu-logo ur-logo

Candidates for Languages that Cannot be Accepted in an Overhead-Free Way

Conjecture

double-palindromes  ∉ DOF.

Conjecture {ww | w ∈ {0, 1}^{∗}} ∉ NOF.

Proving the first conjecture would show DOF ⊊ NOF.

Models Power of the Model Limitations of the Model Summary  Strict Inclusion  tu-logo ur-logo

Candidates for Languages that Cannot be Accepted in an Overhead-Free Way

Theorem double-palindromes ∈ DOF.

Conjecture {ww | w ∈ {0, 1}^{∗}} ∉ NOF.

Proving the first conjecture would show DOF ⊊ NOF.

Models Power of the Model Limitations of the Model Summary  Summary Further Reading  tu-logo ur-logo

Summary

Overhead-free computation is a more faithful model of fixed-size memory. Overhead-free computation is less powerful than linear space. Many context-free languages can be accepted by overhead-free machines. We conjecture that all context-free languages are in NOF_{poly}. Our results can be seen as new results on the power of linear bounded automata with fixed alphabet size.

Models Power of the Model Limitations of the Model Summary  Summary Further Reading  tu-logo ur-logo

For Further Reading

A. Salomaa. Formal Languages. Academic Press, 1973.

E. Dijkstra. Smoothsort, an alternative for sorting in situ. Science of Computer Programming, 1(3):223–233, 1982.

E. Feldman and J. Owings, Jr. A class of universal linear bounded automata. Information Sciences, 6:187–190, 1973.

P. Jančar, F. Mráz, M. Plátek, and J. Vogel. Restarting automata. FCT Conference 1995, LNCS 985, pages 282–292. 1995.

A. Salomaa. Formal Languages. Academic Press, 1973.

E. Dijkstra. Smoothsort, an alternative for sorting in situ. Science of Computer Programming, 1(3):223–233, 1982.

E. Feldman and J. Owings, Jr. A class of universal linear bounded automata. Information Sciences, 6:187–190, 1973.

P. Jančar, F. Mráz, M. Plátek, and J. Vogel. Restarting automata. FCT Conference 1995, LNCS 985, pages 282–292. 1995.

A. Salomaa. Formal Languages. Academic Press, 1973.

E. Dijkstra. Smoothsort, an alternative for sorting in situ. Science of Computer Programming, 1(3):223–233, 1982.

E. Feldman and J. Owings, Jr. A class of universal linear bounded automata. Information Sciences, 6:187–190, 1973.

P. Jančar, F. Mráz, M. Plátek, and J. Vogel. Restarting automata. FCT Conference 1995, LNCS 985, pages 282–292. 1995.

A. Salomaa. Formal Languages. Academic Press, 1973.

E. Dijkstra. Smoothsort, an alternative for sorting in situ. Science of Computer Programming, 1(3):223–233, 1982.

E. Feldman and J. Owings, Jr. A class of universal linear bounded automata. Information Sciences, 6:187–190, 1973.

P. Jančar, F. Mráz, M. Plátek, and J. Vogel. Restarting automata. FCT Conference 1995, LNCS 985, pages 282–292. 1995.

Appendix  Complete Languages Improvements for Context-Free Languages Abbreviations  tu-logo ur-logo

Appendix Outline

4 Appendix

Complete Languages Improvements for Context-Free Languages Abbreviations

Appendix  Complete Languages Improvements for Context-Free Languages Abbreviations  tu-logo ur-logo

Overhead-Free Languages can be PSPACE-Complete

Theorem DOF contains languages that are complete for PSPACE.

Proof.

1 Let A ∈ DLINSPACEbe PSPACE-complete.

Such languages are known to exist. 2 Let M be a linear space machine that accepts A ⊆ {0, 1}^{∗}

with tape alphabet Γ. 3 Let h: Γ → {0, 1}^{∗} be an isometric, injective

homomorphism. 4 Then h(L) is in DOF and it is PSPACE-complete.

Return

Appendix  Complete Languages Improvements for Context-Free Languages Abbreviations  tu-logo ur-logo

Improvements

Theorem 1 DCFL⊆ DOF_{poly}. 2 CFL⊆ NOF_{poly}.

Hemaspaandra, Mukherji, Tantau  Computation with Absolutely No Space Overhead  79

Appendix  Complete Languages Improvements for Context-Free Languages Abbreviations  tu-logo ur-logo

Explanation of Different Abbreviations

DOF  Deterministic Overhead-Free.
NOF  Nondeterministic Overhead-Free.
DOF_{poly} Deterministic Overhead-Free, polynomial time.
DOF_{poly} Nondeterministic Overhead-Free, polynomial time.

Table: Explanation of what different abbreviations mean.