k-counting automata

Joël Allred; Ulrich Ultes-Nitsche

RAIRO - Theoretical Informatics and Applications (2012)

  • Volume: 46, Issue: 4, page 461-478
  • ISSN: 0988-3754

Abstract

top
In this paper, we define k-counting automata as recognizers for ω-languages, i.e. languages of infinite words. We prove that the class of ω-languages they recognize is a proper extension of the ω-regular languages. In addition we prove that languages recognized by k-counting automata are closed under Boolean operations. It remains an open problem whether or not emptiness is decidable for k-counting automata. However, we conjecture strongly that it is decidable and give formal reasons why we believe so.

How to cite

top

Allred, Joël, and Ultes-Nitsche, Ulrich. "k-counting automata." RAIRO - Theoretical Informatics and Applications 46.4 (2012): 461-478. <http://eudml.org/doc/221989>.

@article{Allred2012,
abstract = {In this paper, we define k-counting automata as recognizers for ω-languages, i.e. languages of infinite words. We prove that the class of ω-languages they recognize is a proper extension of the ω-regular languages. In addition we prove that languages recognized by k-counting automata are closed under Boolean operations. It remains an open problem whether or not emptiness is decidable for k-counting automata. However, we conjecture strongly that it is decidable and give formal reasons why we believe so.},
author = {Allred, Joël, Ultes-Nitsche, Ulrich},
journal = {RAIRO - Theoretical Informatics and Applications},
keywords = {ω-automata; extensions to regularω-languages; closure under Boolean operations; emptiness problem; infinite hierarchy ofω-languages},
language = {eng},
month = {11},
number = {4},
pages = {461-478},
publisher = {EDP Sciences},
title = {k-counting automata},
url = {http://eudml.org/doc/221989},
volume = {46},
year = {2012},
}

TY - JOUR
AU - Allred, Joël
AU - Ultes-Nitsche, Ulrich
TI - k-counting automata
JO - RAIRO - Theoretical Informatics and Applications
DA - 2012/11//
PB - EDP Sciences
VL - 46
IS - 4
SP - 461
EP - 478
AB - In this paper, we define k-counting automata as recognizers for ω-languages, i.e. languages of infinite words. We prove that the class of ω-languages they recognize is a proper extension of the ω-regular languages. In addition we prove that languages recognized by k-counting automata are closed under Boolean operations. It remains an open problem whether or not emptiness is decidable for k-counting automata. However, we conjecture strongly that it is decidable and give formal reasons why we believe so.
LA - eng
KW - ω-automata; extensions to regularω-languages; closure under Boolean operations; emptiness problem; infinite hierarchy ofω-languages
UR - http://eudml.org/doc/221989
ER -

References

top
  1. B. Alpern and F.B. Schneider, Defining liveness. Inf. Process. Lett.21 (1985) 181–185.  Zbl0575.68030
  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.68124
  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. M. Bojańczyk, C. David, A. Muscholl, T. Schwentick and L. Segoufin, Two-variable logic on data words. ACM Trans. Comput. Logic12 (2011) 27 :1–27 :26.  Zbl06483152
  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.  
  6. H. Fernau and R. Stiebe, Blind counter automata on ω-words. Fundam. Inform.83 (2008) 51–64.  Zbl1147.68038
  7. P.C. Fischer, Turing machines with restricted memory access. Inf. Control9 (1966) 364–379.  Zbl0145.24205
  8. K. Hashiguchi, Algorithms for determining relative star height and star height. Inf. Comput.78 (1988) 124–169.  Zbl0668.68081
  9. J.E. Hopcroft, R. Motwani and J.D. Ullman, Introduction to Automata Theory, Languages and Computation. Addison Wesley, Pearson Education (2006).  Zbl0980.68066
  10. R.M. Karp and R.E. Miller, Parallel program schemata. J. Comput. Syst. Sci.3 (1969) 147–195.  Zbl0198.32603
  11. R.P. Kurshan, Computer-Aided Verification of Coordinating Processes, 1st edition. Princeton University Press, Princeton, New Jersey (1994).  Zbl0822.68116
  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.  
  13. R. McNaughton, Testing and generating infinite sequences by a finite automaton. Inf. Control9 (1966) 521–530.  Zbl0212.33902
  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.00802
  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. C.A. Petri, Kommunikation mit Automaten. Ph.D. thesis, Rheinisch-Westfälisches Institut für instrumentelle Mathematik an der Universität Bonn (1962).  
  17. H.G. Rice, Classes of recursively enumerable sets and their decision problems. Trans. Amer. Math. Soc.74 (1953) 358–366.  Zbl0053.00301
  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.68316
  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.68402
  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 Reliability13 (2003) 241–255.  
  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. M.Y. Vardi and P. Wolper, Reasoning about infinite computations. Inform. Comput.115 (1994) 1–37.  Zbl0827.03009

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.