Linearly bounded infinite graphs

DOI10.1007/S00236-006-0022-ZzbMATH Open1102.68056arXiv0705.3487OpenAlexW3102239021MaRDI QIDQ852011FDOQ852011

Antoine Meyer, Arnaud Carayol

Publication date: 27 November 2006

Published in: Acta Informatica (Search for Journal in Brave)

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.

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• 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
• The method of forced enumeration for nondeterministic automata
• The monadic second-order logic of graphs, II: Infinite graphs of bounded width
• The theory of ends, pushdown automata, and second-order logic
• Synchronized rational relations of finite and infinite words
• Classes of languages and linear-bounded automata
• On infinite transition graphs having a decidable monadic theory
• Decidability of bisimulation equivalence for normed pushdown processes
• On the transition graphs of Turing machines.
• The synchronized graphs trace the context-sensitive languages
• Context-Sensitive Languages, Rational Graphs and Determinism
• An internal presentation of regular graphs by prefix-recognizable graphs

Cited In (4)

• Title not available (Why is that?)
• Title not available (Why is that?)
• Graphoidally independent infinite graphs
• An Infinite Automaton Characterization of Double Exponential Time

   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 👍 👎
• Title not available (Why is that?) 👍 👎

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)