Some negative results concerning DPDA's
type: Item
instance of: scholarly article
title: Some negative results concerning DPDA's
zbMATH Open document ID: 0564.68058
DOI: 10.1016/0020-0190(84)90008-5
published in: Information Processing Letters
publication date: 1984-01-01T00:00:00Z
review text: Bekanntlich definiert ein DPDA eine Abbildung L: Für jede Konfiguration c ist L(c) die mit c als Start akzeptierte Sprache. \(c_ 1\) und \(c_ 2\) heißen äquivalent genau dann, wenn \(L(c_ 1)=L(c_ 2)\) gilt. Die Arbeit ist eine Warnung davor, die Komplexität von L zu unterschätzen. Unter anderem wird gezeigt: Die Menge \(\{\) \(c|\) L(c) ist regulär\(\}\) ist im allgemeinen nicht kontextfrei. Die Äquivalenzklasse einer Konfiguration c ist im allgemeinen nicht regulär. Äquivalenz als Relation über dem Monoid der Zustands- und Kellerzeichen ist im allgemeinen keine rationale Transduction.
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 68Q05
zbMATH DE Number: 3900181
zbMATH Keywords: deterministic pushdown automaton
zbMATH Keywords: rational transduction
reviewed by: U. Klemm
MaRDI profile type: Publication
full work available at URL: 0020-0190(84)90008-5
OpenAlex ID: W2088734950
cites work: A representation of trees by languages. I
cites work: New families of non real time dpda's and their decidability results
cites work: The equivalence problem for real-time strict deterministic languages
author: Bruno Courcelle
description: scientific article; zbMATH DE number 3900181