Co-occurrence matrix

2013-11-12T12:46:35Z

222.155.176.247: /* Aliases */ Gray-Level Co-occurrence Histograms

A [[regular language]] is said to be '''star-free''' if it can be described by a [[regular expression]] constructed from the letters of the [[alphabet (computer science)|alphabet]], the [[empty set]] symbol, all [[boolean operators]] – including [[Complement (set theory)|complementation]] – and [[concatenation]] but no [[Kleene star]].<ref name=Law235>Lawson (2004) p.235</ref> For instance, the language of words over the alphabet <math>\{a,\,b\}</math> that do not have consecutive a's can be defined by <math>(\emptyset^c aa \emptyset^c)^c</math>, where <math>X^c</math> denotes the complement of a subset <math>X</math> of <math>\{a,\,b\}^*</math>. The condition is equivalent to having [[generalized star height]] zero.

[[Marcel-Paul Schützenberger]] characterized star-free languages as those with [[Aperiodic monoid|aperiodic]] [[syntactic monoid]]s.<ref>{{cite journal | author=[[Marcel-Paul Schützenberger]] | title=On finite monoids having only trivial subgroups | journal=Information and Computation| year=1965| volume=8 | issue=2 | pages=190–194|url=http://igm.univ-mlv.fr/~berstel/Mps/Travaux/A/1965-4TrivialSubgroupsIC.pdf}}</ref><ref name=Law262>Lawson (2004) p.262</ref> They can also be characterized logically as languages definable in FO[<], the monadic [[first-order logic]] over the natural numbers with the less-than relation,<ref>{{cite book | last=Straubing | first=Howard | title=Finite automata, formal logic, and circuit complexity | series=Progress in Theoretical Computer Science | location=Basel | publisher=Birkhäuser | year=1994 | isbn=3-7643-3719-2 | zbl=0816.68086 | page=79 }}</ref> as the [[counter-free language]]s<ref>{{cite book | last1=McNaughton | first1=Robert | last2 = Papert | first2=Seymour | author2-link=Seymour Papert | others=With an appendix by William Henneman | series=Research Monograph | volume=65 | year=1971 | title=Counter-free Automata | publisher=MIT Press | isbn=0-262-13076-9 | zbl=0232.94024 }}</ref> and as languages definable in [[linear temporal logic]].<ref>{{cite book | last = Kamp| first=Johan Antony Willem |authorlink=Hans Kamp | title = Tense Logic and the Theory of Linear Order| publisher = University of California at Los Angeles (UCLA) | year=1968}}</ref>

All star-free languages are in uniform [[AC0|AC<sup>0</sup>]].

==See also==
*[[Star height]]
*[[Generalized star height problem]]
*[[Star height problem]]

==References==
{{reflist}}
* {{cite book | last=Lawson | first=Mark V. | title=Finite automata | publisher=Chapman and Hall/CRC | year=2004 | isbn=1-58488-255-7 | zbl=1086.68074 }}
* {{cite book|editor=Jörg Flum | editor2=Erich Grädel | editor3=Thomas Wilke | title=Logic and automata: history and perspectives | year=2008 | publisher=Amsterdam University Press | isbn=978-90-5356-576-6 | url=http://www.lsv.ens-cachan.fr/Publis/PAPERS/PDF/DG-WT08.pdf | chapter=First-order definable languages | first1=Volker | last1=Diekert | first2=Paul | last2=Gastin | unused_data=chapter}}

{{Formal languages and grammars}}

[[Category:Logic in computer science]]
[[Category:Formal languages]]
[[Category:Automata theory]]

{{comp-sci-theory-stub}}

formulasearchengine - User contributions [en]

Co-occurrence matrix