{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,11]],"date-time":"2025-04-11T04:06:24Z","timestamp":1744344384007,"version":"3.40.4"},"reference-count":22,"publisher":"EDP Sciences","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["RAIRO-Theor. Inf. Appl."],"published-print":{"date-parts":[[2012,10]]},"DOI":"10.1051\/ita\/2012021","type":"journal-article","created":{"date-parts":[[2012,10,10]],"date-time":"2012-10-10T12:20:58Z","timestamp":1349871658000},"page":"461-478","source":"Crossref","is-referenced-by-count":1,"title":["<i>k<\/i>-counting automata"],"prefix":"10.1051","volume":"46","author":[{"given":"Jo\u00ebl","family":"Allred","sequence":"first","affiliation":[]},{"given":"Ulrich","family":"Ultes-Nitsche","sequence":"additional","affiliation":[]}],"member":"250","published-online":{"date-parts":[[2012,10,10]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"Alpern B. and Schneider F.B., Defining liveness.Inf. Process. Lett.21(1985) 181\u2013185.","DOI":"10.1016\/0020-0190(85)90056-0"},{"key":"R2","unstructured":"M. Bojanczyk, Beyond\u03c9-regular languages, inProc. STACS,LIPIcs, edited by J.-Y. Marion and T. Schwentick. Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik5(2010) 11\u201316."},{"key":"R3","doi-asserted-by":"crossref","unstructured":"M. Bojanczyk and T. Colcombet, Boundedness in languages of infinite words. Unpublished manuscript. Extended version of M. Bojanczyk and T. Colcombet, Bounds in\u03c9-Regularity, inLICS(2006) 285\u2013296.","DOI":"10.1109\/LICS.2006.17"},{"key":"R4","doi-asserted-by":"crossref","unstructured":"Boja\u0144czyk M., David C., Muscholl A., Schwentick T. and Segoufin L., Two-variable logic on data words.ACM Trans. Comput. Logic12(2011) 27 :1\u201327 :26.","DOI":"10.1145\/1970398.1970403"},{"key":"R5","unstructured":"J.R. B\u00fcchi, On a decision method in restricted second order arithmetic, inProc. of the International Congress on Logic, Methodology and Philosophy of Science 1960, edited by E. Nagelet al.Stanford University Press (1962) 1\u201311."},{"key":"R6","unstructured":"Fernau H. and Stiebe R., Blind counter automata on\u03c9-words.Fundam. Inform.83(2008) 51\u201364."},{"key":"R7","doi-asserted-by":"crossref","unstructured":"Fischer P.C., Turing machines with restricted memory access.Inf. Control9(1966) 364\u2013379.","DOI":"10.1016\/S0019-9958(66)80003-7"},{"key":"R8","unstructured":"Hashiguchi K., Algorithms for determining relative star height and star height.Inf. Comput.78(1988) 124\u2013169."},{"key":"R9","unstructured":"J.E. Hopcroft, R. Motwani and J.D. Ullman,Introduction to Automata Theory, Languages and Computation. Addison Wesley, Pearson Education (2006)."},{"key":"R10","doi-asserted-by":"crossref","unstructured":"Karp R.M. and Miller R.E., Parallel program schemata.J. Comput. Syst. Sci.3(1969) 147\u2013195.","DOI":"10.1016\/S0022-0000(69)80011-5"},{"key":"R11","doi-asserted-by":"crossref","unstructured":"R.P. Kurshan,Computer-Aided Verification of Coordinating Processes, 1st edition. Princeton University Press, Princeton, New Jersey (1994).","DOI":"10.1515\/9781400864041"},{"key":"R12","doi-asserted-by":"crossref","unstructured":"E.W. Mayr, An algorithm for the general petri net reachability problem, inProc of the 13th Annual ACM Symposium on Theory of Computing,STOC\u201981. New York, USA, ACM (1981) 238\u2013246.","DOI":"10.1145\/800076.802477"},{"key":"R13","doi-asserted-by":"crossref","unstructured":"McNaughton R., Testing and generating infinite sequences by a finite automaton.Inf. Control9(1966) 521\u2013530.","DOI":"10.1016\/S0019-9958(66)80013-X"},{"key":"R14","unstructured":"Minsky M.L., Recursive unsolvability of post\u2019s problem of \u201ctag\u201d and other topics in theory of turing machines.Ann. Math.74(1961) 437\u2013455."},{"key":"R15","doi-asserted-by":"crossref","unstructured":"D.E. Muller, Infinite sequences and infinite machines, inAIEE Proc. of the 4th Annual Symposium on Switching Theory and Logical Design(1963) 3\u201316.","DOI":"10.1109\/SWCT.1963.8"},{"key":"R16","unstructured":"C.A. Petri,Kommunikation mit Automaten. Ph.D. thesis, Rheinisch-Westf\u00e4lisches Institut f\u00fcr instrumentelle Mathematik an der Universit\u00e4t Bonn (1962)."},{"key":"R17","unstructured":"Rice H.G., Classes of recursively enumerable sets and their decision problems.Trans. Amer. Math. Soc.74(1953) 358\u2013366."},{"key":"R18","doi-asserted-by":"crossref","unstructured":"W. Thomas, Automata on infinite objects, inFormal Models and Semantics, edited by J. van Leeuwen.Handbook of Theoret. Comput. Sci.B(1990) 133\u2013191.","DOI":"10.1016\/B978-0-444-88074-1.50009-3"},{"key":"R19","unstructured":"Ultes-Nitsche U., A power-set construction for reducing B\u00fcchi automata to non-determinism degree two.Inform. Process. Lett.101(2007) 107\u2013111."},{"key":"R20","doi-asserted-by":"crossref","unstructured":"Ultes-Nitsche U. and James S.St., Improved verification of linear-time properties within fairness \u2013 weakly continuation-closed behaviour abstractions computed from trace reductions.Software Testing, Verification and Reliability13(2003) 241\u2013255.","DOI":"10.1002\/stvr.280"},{"key":"R21","unstructured":"M.Y. Vardi and P. Wolper, An automata-theoretic approach to automatic program verification, inProc. of the 1st Symposium on Logic in Computer Science. Cambridge (1986)."},{"key":"R22","unstructured":"Vardi M.Y. and Wolper P., Reasoning about infinite computations.Inform. Comput.115(1994) 1\u201337."}],"container-title":["RAIRO - Theoretical Informatics and Applications"],"original-title":[],"link":[{"URL":"http:\/\/www.rairo-ita.org\/10.1051\/ita\/2012021\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,10]],"date-time":"2025-04-10T10:18:39Z","timestamp":1744280319000},"score":1,"resource":{"primary":{"URL":"http:\/\/www.rairo-ita.org\/10.1051\/ita\/2012021"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,10]]},"references-count":22,"journal-issue":{"issue":"4"},"alternative-id":["ita110033"],"URL":"https:\/\/doi.org\/10.1051\/ita\/2012021","relation":{},"ISSN":["0988-3754","1290-385X"],"issn-type":[{"type":"print","value":"0988-3754"},{"type":"electronic","value":"1290-385X"}],"subject":[],"published":{"date-parts":[[2012,10]]}}}