k-counting automata

 Access to full text

1. [1] B. Alpern and F.B. Schneider, Defining liveness. Inf. Process. Lett.21 (1985) 181–185. Zbl0575.68030MR815216
2. [2] M. Bojanczyk, Beyond ω-regular languages, in Proc. STACS, LIPIcs, edited by J.-Y. Marion and T. Schwentick. Schloss Dagstuhl – Leibniz-Zentrum für Informatik 5 (2010) 11–16. Zbl1230.68124MR2853905
3. [3] M. Bojanczyk and T. Colcombet, Boundedness in languages of infinite words. Unpublished manuscript. Extended version of M. Bojanczyk and T. Colcombet, Bounds in ω-Regularity, in LICS (2006) 285–296. 
4. [4] M. Bojańczyk, C. David, A. Muscholl, T. Schwentick and L. Segoufin, Two-variable logic on data words. ACM Trans. Comput. Logic 12 (2011) 27 :1–27 :26. Zbl06483152MR2820102
5. [5] J.R. Büchi, On a decision method in restricted second order arithmetic, in Proc. of the International Congress on Logic, Methodology and Philosophy of Science 1960, edited by E. Nagel et al. Stanford University Press (1962) 1–11. Zbl0147.25103MR183636
6. [6] H. Fernau and R. Stiebe, Blind counter automata on ω-words. Fundam. Inform.83 (2008) 51–64. Zbl1147.68038MR2389126
7. [7] P.C. Fischer, Turing machines with restricted memory access. Inf. Control9 (1966) 364–379. Zbl0145.24205MR199061
8. [8] K. Hashiguchi, Algorithms for determining relative star height and star height. Inf. Comput.78 (1988) 124–169. Zbl0668.68081MR955580
9. [9] J.E. Hopcroft, R. Motwani and J.D. Ullman, Introduction to Automata Theory, Languages and Computation. Addison Wesley, Pearson Education (2006). Zbl0426.68001MR645539
10. [10] R.M. Karp and R.E. Miller, Parallel program schemata. J. Comput. Syst. Sci.3 (1969) 147–195. Zbl0198.32603MR246720
11. [11] R.P. Kurshan, Computer-Aided Verification of Coordinating Processes, 1st edition. Princeton University Press, Princeton, New Jersey (1994). Zbl0822.68116MR1313501
12. [12] E.W. Mayr, An algorithm for the general petri net reachability problem, in Proc of the 13th Annual ACM Symposium on Theory of Computing, STOC’81. New York, USA, ACM (1981) 238–246. Zbl0563.68057
13. [13] R. McNaughton, Testing and generating infinite sequences by a finite automaton. Inf. Control9 (1966) 521–530. Zbl0212.33902MR213241
14. [14] M.L. Minsky, Recursive unsolvability of post’s problem of “tag” and other topics in theory of turing machines. Ann. Math.74 (1961) 437–455. Zbl0105.00802MR140405
15. [15] D.E. Muller, Infinite sequences and infinite machines, in AIEE Proc. of the 4th Annual Symposium on Switching Theory and Logical Design (1963) 3–16. 
16. [16] C.A. Petri, Kommunikation mit Automaten. Ph.D. thesis, Rheinisch-Westfälisches Institut für instrumentelle Mathematik an der Universität Bonn (1962). MR158806
17. [17] H.G. Rice, Classes of recursively enumerable sets and their decision problems. Trans. Amer. Math. Soc.74 (1953) 358–366. Zbl0053.00301MR53041
18. [18] W. Thomas, Automata on infinite objects, in Formal Models and Semantics, edited by J. van Leeuwen. Handbook of Theoret. Comput. Sci. B (1990) 133–191. Zbl0900.68316MR1127189
19. [19] U. Ultes-Nitsche, A power-set construction for reducing Büchi automata to non-determinism degree two. Inform. Process. Lett.101 (2007) 107–111. Zbl1185.68402MR2287328
20. [20] U. Ultes-Nitsche and S.St. James, Improved verification of linear-time properties within fairness – weakly continuation-closed behaviour abstractions computed from trace reductions. Software Testing, Verification and Reliability 13 (2003) 241–255. 
21. [21] M.Y. Vardi and P. Wolper, An automata-theoretic approach to automatic program verification, in Proc. of the 1st Symposium on Logic in Computer Science. Cambridge (1986). 
22. [22] M.Y. Vardi and P. Wolper, Reasoning about infinite computations. Inform. Comput.115 (1994) 1–37. Zbl0827.03009MR1303019