Linearly bounded infinite graphs

DOI10.1007/S00236-006-0022-ZMaRDI QIDQ852011zbMATH OpenOpenAlexFDO

Authors Arnaud Carayol, Antoine Meyer

Publication date 27 November 2006

Published in Acta Informatica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0705.3487

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Grammars and rewriting systems (68Q42)

Abstract: Linearly bounded Turing machines have been mainly studied as acceptors for context-sensitive languages. We define a natural class of infinite automata representing their observable computational behavior, called linearly bounded graphs. These automata naturally accept the same languages as the linearly bounded machines defining them. We present some of their structural properties as well as alternative characterizations in terms of rewriting systems and context-sensitive transductions. Finally, we compare these graphs to rational graphs, which are another class of automata accepting the context-sensitive languages, and prove that in the bounded-degree case, rational graphs are a strict sub-class of linearly bounded graphs.

Recommendations

• Mathematical Foundations of Computer Science 2005
• Context-Sensitive Languages, Rational Graphs and Determinism
• Families of automata characterizing context-sensitive languages
• Traces of term-automatic graphs
• Publication:4934344

Cites work

• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 42752 (Why is no real title available?)
• scientific article; zbMATH DE number 1512622 (Why is no real title available?)
• scientific article; zbMATH DE number 1556866 (Why is no real title available?)
• scientific article; zbMATH DE number 1929936 (Why is no real title available?)
• scientific article; zbMATH DE number 2087217 (Why is no real title available?)
• scientific article; zbMATH DE number 1834676 (Why is no real title available?)
• scientific article; zbMATH DE number 2102748 (Why is no real title available?)
• scientific article; zbMATH DE number 1390078 (Why is no real title available?)
• An internal presentation of regular graphs by prefix-recognizable graphs
• Classes of languages and linear-bounded automata
• Context-Sensitive Languages, Rational Graphs and Determinism
• Decidability of bisimulation equivalence for normed pushdown processes
• Decomposing a $k$-valued transducer into $k$ unambiguous ones
• Nondeterministic Space is Closed under Complementation
• On Relations Defined by Generalized Finite Automata
• On certain formal properties of grammars
• On infinite transition graphs having a decidable monadic theory
• On the transition graphs of Turing machines.
• Synchronized rational relations of finite and infinite words
• The method of forced enumeration for nondeterministic automata
• The monadic second-order logic of graphs, II: Infinite graphs of bounded width
• The synchronized graphs trace the context-sensitive languages
• The theory of ends, pushdown automata, and second-order logic

Cited in

(6)

• scientific article; zbMATH DE number 1390078 (Why is no real title available?)
• scientific article; zbMATH DE number 3023865 (Why is no real title available?)
• Graphoidally independent infinite graphs
• Mathematical Foundations of Computer Science 2005
• An Infinite Automaton Characterization of Double Exponential Time
• Linear languages of finite and infinite words

This page was built for publication: Linearly bounded infinite graphs

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