Paper Info
Title
Traces of Term-Automatic Graphs
Abstract
Abstract In formal language theory, many families of languages are dened using grammars or nite ac- ceptors like pushdown automata and Turing machines. For instance, context-sensitive languages are the languages generated by growing grammars, or equivalently the languages accepted by Turing machines whose work tape size is proportional to that of their input. A few years ago, a new characterization of context-sensitive languages as the path languages of rational graphs (innite graphs dened,by sets of nite-state transducers) was established. We inves- tigate a similar characterization in the more general framework of graphs dened,by term transducers. In particular, we show that the languages of term-automatic graphs between regular sets of vertices coincide with the languages accepted by alternating linearly bounded Turing machines, which form the complexity class ETIME. As a technical tool, we also introduce an arborescent variant of tiling systems, which provides yet another characterization of these languages.
Year
DOI
Venue
2008
10.1007/978-3-540-74456-6_44
Mathematical Foundations of Computer Science
Keywords
Field
DocType
term-automatic graph,arborescent variant,term transducers,similar characterisation,turing machine,finite-state transducers,new characterisation,linearly bounded turing machine,formal language theory,finite acceptors,context-sensitive language,complexity class,formal language,pushdown automata
Discrete mathematics,Combinatorics,Context-free language,Formal language,Nested word,Turing completeness,Computer science,Abstract family of languages,Super-recursive algorithm,Computability,Cone (formal languages)
Journal
Volume
Issue
ISSN
42
3
0302-9743
ISBN
Citations 
PageRank 
3-540-74455-X
2
0.39
References 
Authors
11
1
Name
Order
Citations
PageRank
Antoine Meyer1794.69