License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2014.161
URN: urn:nbn:de:0030-drops-48409
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2014/4840/
Go to the corresponding LIPIcs Volume Portal

Almagor, Shaull ; Kuperberg, Denis ; Kupferman, Orna

Regular Sensing

pdf-format:
16.pdf (0.5 MB)

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.

BibTeX - Entry

@InProceedings{almagor_et_al:LIPIcs:2014:4840,
  author =	{Shaull Almagor and Denis Kuperberg and Orna Kupferman},
  title =	{{Regular Sensing}},
  booktitle =	{34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014)},
  pages =	{161--173},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-77-4},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{29},
  editor =	{Venkatesh Raman and S. P. Suresh},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2014/4840},
  URN =		{urn:nbn:de:0030-drops-48409},
  doi =		{10.4230/LIPIcs.FSTTCS.2014.161},
  annote =	{Keywords: Automata, regular languages, omega-regular languages, complexity, sensing, minimization}
}

Keywords: Automata, regular languages, omega-regular languages, complexity, sensing, minimization
Collection: 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014)
Issue Date: 2014
Date of publication: 12.12.2014

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI