scientific article; zbMATH DE number 3876636

MaRDI QIDQ3341935zbMATH OpenFDO

Authors Burchard von Braunmühl, Rutger Verbeek

Publication date 1983

zbMATH Keywords

algorithm for the recognition of input driven languagescontext-free languagespebbling complexityspace complexity

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 3885334
• Input-driven stack automata
• One pebble versus n bits
• State complexity of operations on input-driven pushdown automata
• Input-driven double-head pushdown automata

Cited in

(21)

• A new complete language for DSPACE(log n)
• Additive number theory via automata theory
• Weighted operator precedence languages
• Beyond operator-precedence grammars and languages
• Operator precedence temporal logic and model checking
• Trimming visibly pushdown automata
• The word problem for visibly pushdown languages described by grammars
• Operator precedence languages: their automata-theoretic and logic characterization
• Descriptional complexity of input-driven pushdown automata
• scientific article; zbMATH DE number 3885334 (Why is no real title available?)
• Sums of Palindromes: an Approach via Automata
• Temporal logic and model checking for operator precedence languages
• On the Complexity of Membership and Counting in Height-Deterministic Pushdown Automata
• Sliding windows over context-free languages
• Higher-order operator precedence languages
• Input-driven double-head pushdown automata
• Weighted operator precedence languages
• Leaf languages and string compression
• Input-Driven Double-Head Pushdown Automata
• Aperiodicity, Star-freeness, and First-order Logic Definability of Operator Precedence Languages
• Arithmetizing classes around {\textsf{NC}}\(^{1}\) and {\textsf{L}}

This page was built for publication:

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