scientific article

zbMath0549.68082MaRDI QIDQ3341935

Rutger Verbeek, Burchard von Braunmühl

Publication date: 1983

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

context-free languagesspace complexityalgorithm for the recognition of input driven languagespebbling complexity

Mathematics Subject Classification ID

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

Related Items

Descriptional Complexity of Input-Driven Pushdown Automata ⋮ Operator Precedence Languages: Their Automata-Theoretic and Logic Characterization ⋮ Beyond operator-precedence grammars and languages ⋮ On the Complexity of Membership and Counting in Height-Deterministic Pushdown Automata ⋮ Input-Driven Double-Head Pushdown Automata ⋮ Aperiodicity, Star-freeness, and First-order Logic Definability of Operator Precedence Languages ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Operator precedence temporal logic and model checking ⋮ The word problem for visibly pushdown languages described by grammars ⋮ Additive number theory via automata theory ⋮ Arithmetizing classes around {\textsf{NC}}\(^{1}\) and {\textsf{L}} ⋮ Leaf languages and string compression ⋮ Weighted operator precedence languages ⋮ Weighted Operator Precedence Languages ⋮ Trimming visibly pushdown automata ⋮ Sums of Palindromes: an Approach via Automata