Regular languages viewed from a graph-theoretic perspective

DOI10.1016/j.ic.2016.06.012zbMath1362.68146OpenAlexW2410277739MaRDI QIDQ515689

Hans Ulrich Simon, Marius Konitzer

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

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Schur numbers and the Ramsey numbers N(3,3,\dots ,3;2)
• Practical arbitrary lookahead LR parsing
• Relationships between nondeterministic and deterministic tape complexities
• LR-regular grammars - an extension of LR(k) grammars
• Upper bounds for ramsey numbers R(3, 3, ?, 3) and Schur numbers
• A survey of bounds for classical Ramsey numbers
• DFA with a Bounded Activity Level
• On the translation of languages from left to right

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