Regular languages viewed from a graph-theoretic perspective

DOI10.1016/J.IC.2016.06.012zbMATH Open1362.68146OpenAlexW2410277739MaRDI QIDQ515689FDOQ515689

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

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

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)

Cites Work

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

Cited In (4)

• Recognizability of graph and pattern languages
• Title not available (Why is that?)
• Title not available (Why is that?)
• Language theoretic properties of regular DAG languages

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)