Regular languages viewed from a graph-theoretic perspective

DOI10.1016/J.IC.2016.06.012MaRDI QIDQ515689zbMATH OpenOpenAlexFDO

Authors Marius Konitzer, Hans Ulrich Simon

Publication date 16 March 2017

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ic.2016.06.012

zbMATH Keywords

computational complexityregular languageclique numbermaximum degreelookahead DFA

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Language theoretic properties of regular DAG languages
• scientific article; zbMATH DE number 3843141
• Two Algorithms For Languages Recognized By Graph Algebras
• Towards a theory of complexity of regular languages
• A graph-based regularity test for deterministic context-free languages

Cites work

• scientific article; zbMATH DE number 1693498 (Why is no real title available?)
• scientific article; zbMATH DE number 986407 (Why is no real title available?)
• scientific article; zbMATH DE number 6275682 (Why is no real title available?)
• scientific article; zbMATH DE number 3189697 (Why is no real title available?)
• A survey of bounds for classical Ramsey numbers
• DFA with a Bounded Activity Level
• LR-regular grammars - an extension of LR(k) grammars
• On the translation of languages from left to right
• Practical arbitrary lookahead LR parsing
• Relationships between nondeterministic and deterministic tape complexities
• Schur numbers and the Ramsey numbers N(3,3,\dots ,3;2)
• Upper bounds for ramsey numbers R(3, 3, ?, 3) and Schur numbers

Cited in

(4)

• Recognizability of graph and pattern languages
• Language theoretic properties of regular DAG languages
• scientific article; zbMATH DE number 1822166 (Why is no real title available?)
• scientific article; zbMATH DE number 5218131 (Why is no real title available?)

This page was built for publication: Regular languages viewed from a graph-theoretic perspective

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