The Algebraic Theory of Parikh Automata
作者： Michaël Cadilhac , Andreas Krebs , Pierre McKenzie
DOI: 10.1007/978-3-642-40663-8_7
关键词:
摘要: The Parikh automaton model equips a finite with integer registers and imposes semilinear constraint on the set of their final settings. Here theory typed monoids is used to characterize language classes that arise algebraically. Complexity bounds are derived, such as containment unambiguous automata languages in NC1. Noting DetAPA positive supports rational ℤ-series, further shown stronger than unary langages. This suggests candidates for separating two better known variants uniform
springer.com
sci-hub.st 参考文章(30)
Hervé Caussinus, Denis Thérien, Heribert Vollmer, Pierre McKenzie, Nondeterministic NC 1 Computation. Journal of Computer and System Sciences. ,vol. 57, pp. 200- 212 ,(1998)
Howard Straubing, Finite Automata, Formal Logic, and Circuit Complexity ,(1994)
Jean Berstel, Christophe Reutenauer, Noncommutative Rational Series with Applications Cambridge University Press. ,vol. 137, ,(2010) , 10.1017/CBO9780511760860
Heribert Vollmer, Introduction to Circuit Complexity: A Uniform Approach ,(2010)
Felix Klaedtke, Harald Rueß, Monadic second-order logics with cardinalities international colloquium on automata languages and programming. pp. 681- 696 ,(2003) , 10.1007/3-540-45061-0_54
Michel Fliess, Propriétés booléennes des langages stochastiques Theory of Computing Systems \/ Mathematical Systems Theory. ,vol. 7, pp. 353- 359 ,(1973) , 10.1007/BF01890611
Arto Salomaa, M. Soittola, Automata-theoretic aspects of formal power series ,(1978)
Nutan Limaye, Meena Mahajan, B. V. Raghavendra Rao, Arithmetizing Classes Around NC 1 and L STACS 2007. pp. 477- 488 ,(2007) , 10.1007/978-3-540-70918-3_41
H. Caussinus, P. McKenzie, D. Therien, H. Vollmer, Nondeterministic NC/sup 1/ computation conference on computational complexity. pp. 12- 21 ,(1996) , 10.1109/CCC.1996.507664
Seymour Ginsburg, Edwin Spanier, Semigroups, Presburger formulas, and languages. Pacific Journal of Mathematics. ,vol. 16, pp. 285- 296 ,(1966) , 10.2140/PJM.1966.16.285