scientific article; zbMATH DE number 5201364

MaRDI QIDQ5422229zbMATH OpenFDO

Authors Markus Holzer, Henning Bordihn

Publication date 17 October 2007

Full work available at URL http://www.jucs.org/jucs_8_2/on_the_computational_complexity

zbMATH Keywords

computational complexitydecision problemsformal languagessynchronized grammars

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Grammars and rewriting systems (68Q42) Formal languages and automata (68Q45)

Recommendations

• Synchronization functions of synchronized context-free grammars and languages
• scientific article; zbMATH DE number 2201368
• On the synchronized derivation depth of context-free grammars
• On the context-free production complexity of finite languages
• On computational complexity of contextual languages
• Computational complexity of certain problems related to carefully synchronizing words for partial automata and directing words for nondeterministic automata
• Context-free complexity of finite languages
• Complexity of checking whether two automata are synchronized by the same language
• Language complexity on the synchronous anonymous ring
• Complexity Results on Balanced Context-Free Languages

Cited in

(4)

• Computational complexity of certain problems related to carefully synchronizing words for partial automata and directing words for nondeterministic automata
• On the synchronized derivation depth of context-free grammars
• An infinite hierarchy induced by depth synchronization
• The generative capacity of block-synchronized context-free grammars

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 Q5422229)