[Up]
Logic and branching automata
Copyright informations
The final publication is available at link.springer.com.
Abstract
The first result presented in this paper is the closure under complementation of the class or languages of finite N-free posets recognized by branching automata. Relying on this, we propose a logic, named Presburger-MSO or P-MSO for short, precisely as expressive as branching automata. The P-MSO theory of the class of all finite N-free posets is decidable.
Keywords
N-free posets, series-parallel posets, sp-rational languages, automata, commutative monoids, monadic second-order logic, Presburger logic.
ACM 1998 classification
F.1.1 Models of Computation, F.4.1 Mathematical Logic, F.4.3 Formal Languages
- Ahmed Bouajjani and Tayssir Touili, "On computing reachability sets of
process rewrite systems", in RTA (Jürgen Giesl, ed.), vol. 3467 of
Lecture Notes in Computer Science, pp. 484-499, Springer,
2005.
- J. Richard Büchi, "Weak second-order arithmetic and finite automata",
Zeit. Math. Logik. Grund. Math., vol. 6, pp. 66-92, 1960.
- Silvano Dal-Zilio and Denis Lugiez, "XML Schema, Tree Logic and
Sheaves Automata", in RTA (Robert Nieuwenhuis, ed.), vol. 2706 of
Lecture Notes in Computer Science, pp. 246-263, Springer,
2003.
- Heinz Dieter Ebbinghaus and Jörg Flum, Finite model theory.
Springer monographs in mathematics, Springer, 2nd ed., 1999.
- Calvin C. Elgot, "Decision problems of finite automata design and related
arithmetics", Trans. Amer. Math. Soc., vol. 98, pp. 21-51, Jan.
1961.
- Zoltan Esik and Z.L. Németh, "Automata on series-parallel
biposets", in DLT'2001 (W. Kuich, G. Rozenberg, and A. Salomaa, eds.),
vol. 2295 of Lect. Notes in Comput. Sci., pp. 217-227,
Springer-Verlag, 2002.
- Samuel Eilenberg and Marcel Paul Schützenberger, "Rational sets in
commutative monoids", Journal of Algebra, vol. 13, no. 2, pp. 173-191,
1969.
- Seymour Ginsburg and Edwin H. Spanier, "Semigroups, Presburger formulas,
and languages", Pacific Journal of Mathematics, vol. 16, no. 2, pp.
285-296, 1966.
- H. J. Hoogeboom and P. ten Pas, "Text languages in an algebraic framework",
Fund. Inform., vol. 25, pp. 353-380, 1996.
- H. J. Hoogeboom and P. ten Pas, "Monadic second-order definable languages",
Theory Comput. Syst., vol. 30, pp. 335-354, 1997.
- Stephen C. Kleene, "Representation of events in nerve nets and finite
automata", in Automata studies (Shannon and McCarthy, eds.),
(Princeton, New Jersey), pp. 3-42, Princeton University Press, 1956.
- Dietrich Kuske, "Infinite series-parallel posets: logic and languages", in
ICALP 2000, vol. 1853 of Lect. Notes in Comput. Sci., pp.
648-662, Springer-Verlag, 2000.
- Kamal Lodaya and Pascal Weil, "A Kleene iteration for
parallelism" in Foundations of Software Technology and Theoretical
Computer Science, pp. 355-366, 1998.
- Kamal Lodaya and Pascal Weil, "Series-parallel posets: algebra, automata
and languages", in STACS'98 (M. Morvan, Ch. Meinel, and D. Krob,
eds.), vol. 1373 of Lect. Notes in Comput. Sci., pp. 555-565,
Springer-Verlag, 1998.
- Kamal Lodaya and Pascal Weil, "Series-parallel languages and the
bounded-width property", Theoret. Comput. Sci., vol. 237, no. 1--2,
pp. 347-380, 2000.
- Kamal Lodaya and Pascal Weil, "Rationality in algebras with a series
operation", Inform. Comput., vol. 171, pp. 269-293, 2001.
- Mojzesz Presburger, "Über die vollstandigkeit eines gewissen systems
der arithmetic ganzer zahlen, in welchem die addition als einzige operation
hervortritt", in Proc. Sprawozdaniez I Kongresu Matematykow Krajow
Slowianskich, Warsaw, pp. 92-101, 1930.
English translation: On the completeness of certain system of arithmetic of
whole numbers in which addition occurs as the only operation. Hist.
Philos. Logic, 12:92--101, 1991.
- Jacques Sakarovitch, Eléments de théorie des automates.
Vuibert, 2003.
English (and revised) version: Elements of automata theory, Cambridge
University Press, 2009.
- Helmut Seidl, Thomas Schwentick, and Anca Muscholl, "Counting in trees", in
Logic and Automata (Jörg Flum, Erich Grädel, and Thomas Wilke,
eds.), vol. 2 of Texts in Logic and Games, pp. 575-612, Amsterdam
University Press, 2008.
- Wolfgang Thomas, "Languages, automata, and logic", in Handbook of Formal
Languages (G. Rozenberg and A. Salomaa, eds.), vol. III, pp. 389-455,
Springer-Verlag, 1997.
- Boris Avraamovich Trakhtenbrot, "Finite automata and monadic second order
logic", Siberian Math., vol. 3, pp. 101-131, 1962.
(Russian). English translation in AMS Transl. 59 (1966), 23-55.
- Jacobo Valdes, "Parsing flowcharts and series-parallel graphs", Tech. Rep.
STAN-CS-78-682, Computer science departement of the Stanford University,
Standford, Ca., 1978.
- Jacobo Valdes, Robert E. Tarjan, and Eugene L. Lawler, "The recognition of
series parallel digraphs", SIAM J. Comput., vol. 11, pp. 298-313,
1982.
Download
PDF file (315 Ko)
 |
24 January 2015 22:07:17 |