The Rational Index: A Complexity Measure for Languages
From MaRDI portal
Publication:3923626
DOI10.1137/0210020zbMath0469.68083OpenAlexW2011895459MaRDI QIDQ3923626
Maurice Nivat, Luc Boasson, Bruno Courcelle
Publication date: 1981
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0210020
Related Items (12)
The rational index of the Dyck language \(D_ 1^{'*}\) ⋮ On regular realizability problems for context-free languages ⋮ Rational index of context-free languages in exp \(\Theta(^ p\sqrt{n})\) and \(n^{\Theta((\ln n)^{1/p})}\) ⋮ Rational index of languages with bounded dimension of parse trees ⋮ Context-free languages with rational index in $\Theta (n^\gamma )$ for algebraic numbers $\gamma $ ⋮ Dynamical recognizers: real-time language recognition by analog computers ⋮ On the Degree of Extension of Some Models Defining Non-Regular Languages ⋮ Unnamed Item ⋮ Rational indexes of generators of the cone of context-free languages ⋮ On the degrees of non-regularity and non-context-freeness ⋮ Regular Realizability Problems and Context-Free Languages ⋮ Output string languages of compositions of deterministic macro tree transducers
This page was built for publication: The Rational Index: A Complexity Measure for Languages
