106 Pages
English
Gain access to the library to view online
Learn more

A simple P complete problem and its representations by language equations

-

Gain access to the library to view online
Learn more
106 Pages
English

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


Subjects

Informations

Published by
Reads 140
Language English
Document size 1 MB

Exrait

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