Iterated pushdown automata and sequences of rational numbers

DOI10.1016/J.APAL.2005.12.004MaRDI QIDQ2498918zbMATH OpenOpenAlexFDO

Authors Séverine Fratani, Géraud Sénizergues

Publication date 16 August 2006

Published in Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.apal.2005.12.004

decidability of monadic theories graph theory indexed grammars pushdown automata

Decidability of theories and sets of sentences (03B25) Automata and formal grammars in connection with logical questions (03D05) Grammars and rewriting systems (68Q42) Formal languages and automata (68Q45) Graph theory (including graph drawing) in computer science (68R10)

Review text

The authors of this interesting paper establish formal relations between pushdown automata of positive level and graph-theoretical tree structures. Use is made of various generalizations of M. O. Rabin's tree theorem due to A. Muchnik. Thus, the authors provide an alternative approach for establishing various decidability properties for this automata class. Note that this approach also provides extensions of the basic result of Büchi on the decidability of monadic second-order arithmetic. The reviewer points out that several of the results are easily extended to recursive pushdown automata and r.e. sequences of algebraic numbers. The bibliography contains 35 basic items.

Recommendations

Cites work

Cited in

(10)

This page was built for publication: Iterated pushdown automata and sequences of rational numbers

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