A simple P complete problem and its representations by language equations

Alexander Okhotin

Description

A simple P-complete problem and its representations by language equations Alexander Okhotin University of Turku and Academy of Finland September 13, 2007 Alexander Okhotin Simple P-complete problem and language equations September 13, 2007 1 / 16

• representing hardest


• linear context-free


• language equations


• problem find small


• trellis automata

Informations

• Publié par: pefav
• Nombre de lectures: 140
• Langue: English
• Poids de l'ouvrage: 1 Mo

Extrait

and

Alexander Okhotin

its

A simple represent

P-complete ations by lan

problem guage eq

Alexander Okhotin

uations

University of TurkuandAcademy of Finland

September 13, 2007

Simple P-complete problem and language equations

September 13, 2007

1 / 16

Representing hardest sets

Family of devices.

Alexander Okhotin

Simple P-complete problem and language equations

September 13, 2007

2 / 16

Representing hardest sets

Family of devices.

Alexander Okhotin

1

2

3

Turing machines

Linear context-free grammars

Trellis automata

Simple P-complete problem and language equations

September 13, 2007

2 / 16

Representing hardest sets

Family of devices. Family of languages.

Alexander Okhotin

1

2

3

Turing machines

Linear context-free grammars

Trellis automata

Simple P-complete problem and language equations

September 13, 2007

2 / 16

Representing hardest sets

Family of devices. Family of languages.

Alexander Okhotin

1

2

3

Turing machines: RE Linear context-free grammars: (NL Trellis automata:

Simple P-complete problem and language equations

(P

September 13, 2007

2 / 16

Representing hardest sets

Family of devices. Family of languages.

Hardest set.

Alexander Okhotin

1

2

3

Turing machines: RE Linear context-free grammars: (NL Trellis automata:

Simple P-complete problem and language equations

(P

September 13, 2007

2 / 16

Representing hardest sets

Family of devices. Family of languages.

Hardest set.

Alexander Okhotin

1

2

3

Turing machines: RE-complete Linear context-free grammars: NL-complete Trellis automata:

Simple P-complete problem and language equations

P-complete

September 13, 2007

2 / 16

Representing hardest sets

Family of devices. Family of languages. Hardest set. Its representation.

Alexander Okhotin

1

2

3

Turing machines: RE-complete Linear context-free grammars: NL-complete Trellis automata:

Simple P-complete problem and language equations

P-complete

September 13, 2007

2 / 16

Representing hardest sets

Family of devices. Family of languages. Hardest set. Its representation. Succinctness.

Alexander Okhotin

1

2

3

Turing machines: RE-complete Linear context-free grammars: NL-complete Trellis automata: P-complete

Simple P-complete problem and language equations

September 13, 2007

2 / 16

Representing hardest sets

Family of devices. Family of languages. Hardest set. Its representation. Succinctness.

Motivation:

Alexander Okhotin

1

2

3

Turing machines: RE-complete Linear context-free grammars: NL-complete Trellis automata:

Simple P-complete problem and language equations

P-complete

September 13, 2007

2 / 16