On inverse deterministic pushdown transductions

DOI10.1016/0022-0000(78)90028-4MaRDI QIDQ1245575zbMATH OpenOpenAlexFDO

Authors Walter Savitch, Paul M. B. Vitányi

Publication date 1978

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0022-0000(78)90028-4

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Cites work

• A universal context-free grammar
• Abstract families of deterministic languages
• Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
• Deterministic context free languages
• How to Make Arbitrary Grammars Look Like Context-Free Grammars
• scientific article; zbMATH DE number 3569860 (Why is no real title available?)
• scientific article; zbMATH DE number 3428547 (Why is no real title available?)
• scientific article; zbMATH DE number 3311755 (Why is no real title available?)
• Jump PDA’s and Hierarchies of Deterministic Context-Free Languages
• On the Tape Complexity of Deterministic Context-Free Languages
• Recognition time of context-free languages by on-line Turing machines
• Relationships between nondeterministic and deterministic tape complexities
• Space-bounded reducibility among combinatorial problems
• The Hardest Context-Free Language
• The theory of languages
• Two-way pushdown automata

Cited in

(2)

• On characterizations of recursively enumerable languages
• A note on dpda transductions of {0,1}^∗and inverse dpda transductions of the dyck set

This page was built for publication: On inverse deterministic pushdown transductions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1245575)