Rational graphs trace context-sensitive languages

DOI10.1007/3-540-44683-4_48MaRDI QIDQ4779172zbMATH OpenFDO

Authors Christophe Morvan, Colin Stirling

Publication date 25 November 2002

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL http://link.springer.de/link/service/series/0558/bibs/2136/21360548

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Graph theory (including graph drawing) in computer science (68R10)

Cited in

(8)

• On the transition graphs of Turing machines.
• Families of automata characterizing context-sensitive languages
• On Boolean closed full trios and rational Kripke frames
• Traces of term-automatic graphs
• An Infinite Automaton Characterization of Double Exponential Time
• Context-Sensitive Languages, Rational Graphs and Determinism
• A class of rational trace relations closed under composition
• Linearly bounded infinite graphs

This page was built for publication: Rational graphs trace context-sensitive languages

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