Document Open Access Logo

Regular Sensing

Authors Shaull Almagor, Denis Kuperberg, Orna Kupferman

PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2014.161.pdf
  • Filesize: 482 kB
  • 13 pages

Document Identifiers

Author Details

Shaull Almagor
Denis Kuperberg
Orna Kupferman

Cite As Get BibTex

Shaull Almagor, Denis Kuperberg, and Orna Kupferman. Regular Sensing. In 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 29, pp. 161-173, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014) https://doi.org/10.4230/LIPIcs.FSTTCS.2014.161

Abstract

The size of deterministic automata required for recognizing regular and omega-regular languages is a well-studied measure for the complexity of languages. We introduce and study a new complexity measure, based on the sensing required for recognizing the language. Intuitively, the sensing cost quantifies the detail in which a random input word has to be read in order to decide its membership in the language. We show that for finite words, size and sensing are related, and minimal sensing is attained by minimal automata. Thus, a unique minimal-sensing deterministic automaton exists, and is based on the language's right-congruence relation. For infinite words, the minimal sensing may be attained only by an infinite sequence of automata. We show that the optimal limit cost of such sequences can be characterized by the language's right-congruence relation, which enables us to find the sensing cost of omega-regular languages in polynomial time.

Subject Classification

Keywords
  • Automata
  • regular languages
  • omega-regular languages
  • complexity
  • sensing
  • minimization

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. S. Almagor, U. Boker, and O. Kupferman. Discounting in LTL. In TACAS, Lecture Notes in Computer Science. Springer, 2014. Google Scholar
  2. K. Chatterjee and R. Majumdar. Minimum attention controller synthesis for omega-regular objectives. In FORMATS, pages 145-159, 2011. Google Scholar
  3. K. Chatterjee, R. Majumdar, and T. A. Henzinger. Controller synthesis with budget constraints. In HSCC, volume 4981 of Lecture Notes in Computer Science, pages 72-86. Springer, 2008. Google Scholar
  4. D. L. Donoho. Compressed sensing. IEEE Trans. Inform. Theory, 52:1289-1306, 2006. Google Scholar
  5. C. Grinstead and J. Laurie Snell. Introduction to Probability, chapter 11 (Markov Chains), pages 405-470. American Mathematical Society, 1997. Google Scholar
  6. G. Kindler. Property Testing, PCP, and Juntas. PhD thesis, Tel Aviv University, 2002. Google Scholar
  7. O. Kupferman and M. Y. Vardi. Church’s problem revisited. The Bulletin of Symbolic Logic, 5(2):245 - 263, 1999. Google Scholar
  8. E. Kushilevitz and N. Nisan. Communication complexity. Cambridge University Press, 1997. Google Scholar
  9. C. Mauduit and A. Sárköz. On finite pseudorandom binary sequences. i. measure of pseudorandomness, the legendre symbol. Acta Arith., 82(4):365-377, 1997. Google Scholar
  10. S. Muthukrishnan. Theory of data stream computing: where to go. In Proc. 30th Symposium on Principles of Database Systems, pages 317-319, 2011. Google Scholar
  11. D. Niwinski and I. Walukiewicz. Relating hierarchies of word and tree automata. In STACS, volume 1373 of Lecture Notes in Computer Science. Springer, 1998. Google Scholar
  12. S. Schewe. Beyond Hyper-Minimisation - Minimising DBAs and DPAs is NP-Complete. In FSTTCS, volume 8 of Leibniz International Proceedings in Informatics (LIPIcs), pages 400-411, 2010. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact