Standard

Relating automata-theoretic hierarchies to complexity-theoretic hierarchies. / Selivanov, Victor L.

In: RAIRO - Theoretical Informatics and Applications, Vol. 36, No. 1, 01.01.2002, p. 29-42.

Research output: Contribution to journal › Article › peer-review

Harvard

Selivanov, VL 2002, 'Relating automata-theoretic hierarchies to complexity-theoretic hierarchies', RAIRO - Theoretical Informatics and Applications, vol. 36, no. 1, pp. 29-42. https://doi.org/10.1051/ita:2002003

APA

Selivanov, V. L. (2002). Relating automata-theoretic hierarchies to complexity-theoretic hierarchies. RAIRO - Theoretical Informatics and Applications, 36(1), 29-42. https://doi.org/10.1051/ita:2002003

Vancouver

Selivanov VL. Relating automata-theoretic hierarchies to complexity-theoretic hierarchies. RAIRO - Theoretical Informatics and Applications. 2002 Jan 1;36(1):29-42. https://doi.org/10.1051/ita:2002003

Author

Selivanov, Victor L. / Relating automata-theoretic hierarchies to complexity-theoretic hierarchies. In: RAIRO - Theoretical Informatics and Applications. 2002 ; Vol. 36, No. 1. pp. 29-42.

BibTeX

@article{e7ad859b34be4f279ddade34884162e2,
title = "Relating automata-theoretic hierarchies to complexity-theoretic hierarchies",
abstract = "We show that some natural refinements of the Straubing and Brzozowski hierarchies correspond (via the so called leaf-languages) step by step to similar refinements of the polynomial-time hierarchy. This extends a result of Burtschik and Vollmer on relationship between the Straubing and the polynomial hierarchies. In particular, this applies to the Boolean hierarchy and the plus-hierarchy.",
author = "Selivanov, {Victor L.}",
year = "2002",
month = jan,
day = "1",
doi = "10.1051/ita:2002003",
language = "English",
volume = "36",
pages = "29--42",
journal = "RAIRO - Theoretical Informatics and Applications",
issn = "0988-3754",
publisher = "EDP Sciences",
number = "1",

}

RIS

TY - JOUR

T1 - Relating automata-theoretic hierarchies to complexity-theoretic hierarchies

AU - Selivanov, Victor L.

PY - 2002/1/1

Y1 - 2002/1/1

N2 - We show that some natural refinements of the Straubing and Brzozowski hierarchies correspond (via the so called leaf-languages) step by step to similar refinements of the polynomial-time hierarchy. This extends a result of Burtschik and Vollmer on relationship between the Straubing and the polynomial hierarchies. In particular, this applies to the Boolean hierarchy and the plus-hierarchy.

AB - We show that some natural refinements of the Straubing and Brzozowski hierarchies correspond (via the so called leaf-languages) step by step to similar refinements of the polynomial-time hierarchy. This extends a result of Burtschik and Vollmer on relationship between the Straubing and the polynomial hierarchies. In particular, this applies to the Boolean hierarchy and the plus-hierarchy.

UR - http://www.scopus.com/inward/record.url?scp=14244270816&partnerID=8YFLogxK

U2 - 10.1051/ita:2002003

DO - 10.1051/ita:2002003

M3 - Article

AN - SCOPUS:14244270816

VL - 36

SP - 29

EP - 42

JO - RAIRO - Theoretical Informatics and Applications

JF - RAIRO - Theoretical Informatics and Applications

SN - 0988-3754

IS - 1

ER -

ID: 127141153