Rational index of vector addition systems languages

DOI10.1007/BF00263577MaRDI QIDQ1823002zbMATH OpenOpenAlexFDO

Authors Laurent Pierre, Sylvianne R. Schwer

Publication date 1989

Published in Acta Informatica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf00263577

zbMATH Keywords

context- free languageslower boundPetri netspolynomialsrational indexupper boundV.A.S. languagesVector Addition System

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Recommendations

• Rational index of context-free languages in exp \(\Theta(^ p\sqrt{n})\) and \(n^{\Theta((\ln n)^{1/p})}\)
• Rational indexes of generators of the cone of context-free languages
• On the context-freeness problem for vector addition systems
• Context-free languages with rational index in \Theta (n^\gamma ) for algebraic numbers \gamma
• The rational index of the Dyck language \(D_ 1^{'*}\)

Cited in

(3)

• Rational index of context-free languages in exp \(\Theta(^ p\sqrt{n})\) and \(n^{\Theta((\ln n)^{1/p})}\)
• Context-free languages with rational index in \Theta (n^\gamma ) for algebraic numbers \gamma
• scientific article; zbMATH DE number 3557672 (Why is no real title available?)

This page was built for publication: Rational index of vector addition systems languages

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