Families of automata characterizing context-sensitive languages

In the hierarchy of infinite graph families, rational graphs are defined by rational transducers with labelled final states. This paper proves that their traces are precisely context-sensitive languages and that this result remains true for synchronized rational graphs. [PUBLICATION ABSTRACT]

Saved in:
Bibliographic Details
Published in:Acta informatica 2005-03, Vol.41 (4-5), p.293-314
Main Authors: MORVAN, Christophe, RISPAL, Chloé
Format: Article
Language:English
Subjects:
Applied sciences
Automata. Abstract machines. Turing machines
Combinatorics
Combinatorics. Ordered structures
Computer Science
Computer science
control theory
systems
Discrete Mathematics
Exact sciences and technology
Graph theory
Graphs
Hierarchies
Language theory and syntactical analysis
Mathematics
Sciences and techniques of general use
Studies
Theoretical computing
Transducers
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In the hierarchy of infinite graph families, rational graphs are defined by rational transducers with labelled final states. This paper proves that their traces are precisely context-sensitive languages and that this result remains true for synchronized rational graphs. [PUBLICATION ABSTRACT]
ISSN:0001-5903
1432-0525
DOI:10.1007/s00236-004-0160-0