MPI-INF D1 Publications: Journal Article: The Recognition of Deterministic {CFL}'s in Small Time and Space

Journal Article
@Article
Artikel in Fachzeitschrift

Show entries of:

this year (2023) | last year (2022) | two years ago (2021) | Notes URL

Action:

Options:

Goto entry point

Author, Editor(s)

Author(s):

von Braunmühl, Burchard
Cook, Stephen
Mehlhorn, Kurt
Verbeek, Rutger

dblp
dblp
dblp
dblp

BibTeX cite key*:

mehlhorn83e

Title

Title*:

The Recognition of Deterministic CFL's in Small Time and Space

Journal

Journal Title*:	Information and Control	Journal's URL:
Download URL for the article:		Language:	English

Publisher

Publisher's Name:	Academic Press	Publisher's URL:
Publisher's Address:	New York, NY, USA	ISSN:

Vol, No, pp, Date

Volume*:	56	Number:	1/2
Publishing Date:	1983
Pages*:	34-51	Number of VG Pages:
Page Start:		Page End:
Sequence Number:		DOI:

Note, Abstract, ©

Note:
(LaTeX) Abstract:	Let S(n) be a nice space bound such that log² n S(n) n. Then every DCFL is recognized by a multitape Turing machine simultaneously in time O(n²/S(n)) and space O(S(n)), and this time bound is optimal. If the machine is allowed a random access input, then the time bound can be improved so that the time-space product is O(n^{1 +}).
URL for the Abstract:
Categories, Keywords:
HyperLinks / References / URLs:
Copyright Message:
Personal Comments:
Download Access Level:	Public

Correlation

MPG Unit:	Max-Planck-Institut für Informatik

MPG Subunit:	Algorithms and Complexity Group
Audience:	Expert
Appearance:	MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort

BibTeX Entry:

@ARTICLE{mehlhorn83e,
AUTHOR = {von Braunm{\"u}hl, Burchard and Cook, Stephen and Mehlhorn, Kurt and Verbeek, Rutger},
TITLE = {The Recognition of Deterministic {CFL}'s in Small Time and Space},
JOURNAL = {Information and Control},
PUBLISHER = {Academic Press},
YEAR = {1983},
NUMBER = {1/2},
VOLUME = {56},
PAGES = {34--51},
ADDRESS = {New York, NY, USA},
}

Entry last modified by Anja Becker, 03/06/2008

Edit History (please click the blue arrow to see the details)

	Editor(s) Christine Kiesel	Created 08/06/2006 18:38:33
Revisions 5. 4. 3. 2. 1.	Editor(s) Anja Becker Christine Kiesel Christine Kiesel Christine Kiesel Christine Kiesel	Edit Dates 06.03.2008 09:02:20 12.09.2006 14:22:30 12.09.2006 14:20:45 12.09.2006 10:46:42 12.09.2006 10:46:20

Attachment Section