Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Acta Informatica
Erschienen in: Acta Informatica 3/2013

01.05.2013 | Original Article

Avoiding cross-bifix-free binary words

verfasst von: Stefano Bilotta, Elisabetta Grazzini, Elisa Pergola, Renzo Pinzani

Erschienen in: Acta Informatica | Ausgabe 3/2013

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

In this paper we study the construction and the enumeration of binary words in \(\{0,1\}^*\) having more 1’s than 0’s and avoiding a set of cross-bifix-free patterns. We give a particular succession rule, called jumping and marked succession rule, which describes the growth of such words according to their number of ones. Moreover, the problem of associating a word to a path in the generating tree obtained by the succession rule is solved by introducing an algorithm which constructs all binary words having more 1’s than 0’s and then kills those containing the forbidden patterns. Finally, we give the generating function of such words according to the number of ones.
Nächster Artikel Conjunctive grammars and alternating pushdown automata

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren
Literatur
1.
2.
Bacchelli, S., Barcucci, E., Grazzini, E., Pergola, E.: Exhaustive generation of combinatorial objects by ECO. Acta Inform. 40(8), 585–602 (2004)MathSciNetMATHCrossRef
3.
Bajic, D.: On Construction of Cross-Bifix-Free Kernel Sets, 2nd MCM COST 2100, TD(07) 237. Lisbon, Portugal (2007)
4.
Bajic, D., Drajic, D.: Duration of search for a fixed pattern in random data: distribution function and variance. Electron. lett. 31(8), 631–632 (1995)CrossRef
5.
Bajic, D., Stojanovic, J.: Distributed sequences and search process. In: IEEE International Conference on Communications, ICC2004 Paris, pp. 514–518 (2004)
6.
Banderier, C., Bousquet-Mélou, M., Denise, A., Flajolet, P., Gardy, D., Gouyou-Beauchamps, D.: Generating functions for generating trees. Discret. Math. 246, 29–55 (2002)MATHCrossRef
7.
Barcucci, E., Del Lungo, A., Pergola, E., Pinzani, R.: ECO: a methodology for the enumeration of combinatorial objects. J. Differ. Equ. Appl. 5, 435–490 (1999)MATHCrossRef
8.
Bernini, A., Grazzini, E., Pergola, E., Pinzani, R.: A general exhaustive generation algorithm for gray structures. Acta Inform. 44(5), 361–376 (2007)MathSciNetMATHCrossRef
9.
Bilotta, S., Merlini, D., Pergola, E., Pinzani, R.: Pattern \(1^{j+1}0^j\) avoiding binary words. Fundam. Inform. 177(1–4), 35–55 (2012)MathSciNet
10.
Bilotta, S., Pergola, E., Pinzani, R.: A new approach to cross-bifix-free sets. IEEE Trans. Inf. Theory 58(6), 4058–4063 (2012)MathSciNetCrossRef
11.
Corteel, S.: Séries génératrices exponentielles pour les ECO-systèmes signés. In: Proceedings of the 12th International Conference on Formal Power Series and Algebraic Combinatorics, Moscow (2000)
12.
Ferrari, L., Pergola, E., Pinzani, R., Rinaldi, S.: Jumping succession rules and their generating functions. Discret. Math. 271, 29–50 (2003)MathSciNetMATHCrossRef
13.
14.
15.
Guibas, L.J., Odlyzko, M.: Long repetitive patterns in random sequences. Zeitschrift für Wahrscheinlichkeitstheorie 53, 241–262 (1980)MathSciNetMATHCrossRef
16.
Guibas, L.J., Odlyzko, M.: String overlaps, pattern matching, and nontransitive games. J. Comb. Theory Ser. A 30, 183–208 (1981)MathSciNetMATHCrossRef
17.
18.
Kim, K.H., Putcha, M.S., Roush, F.W.: Some combinatorial properties of free semigroups. J. Lond. Math. Soc. 16(2), 397–402 (1977)
19.
Kumar, S., Spafford, E.H.: A pattern matching model for misuse intrusion detection. In: Computer Security, pp. 11–21 (1994)
20.
Merlini, D., Sprugnoli, R., Verri, M.C.: An Algebra for proper generating tree, In: Algorithms, Trees, Combinatorics and Probabilities, Trends in Mathematics, Mathematics and Computer Science, pp. 127–139 (2000)
21.
Nielsen, P.T.: On the expected duration of a search for a fixed pattern in random data. IEEE Trans. Inform. Theory, IT-29, 702–704 (1973)
22.
Nielsen, P.T.: A Note on Bifix-free sequences. IEEE Trans. Inform. Theory, IT-29, 704–706 (1973)
23.
Rigoutsos, I., Floratos, A., Parida, L., Gao, Y., Platt, D.: The emergence of pattern discovery techniques in computational biology. Metab. Eng. 2, 159–177 (2000)CrossRef
24.
Sedgewick, R., Flajolet, P.: An Introduction to the Analysis of Algorithms. Chapman-Hall, London (1995)
25.
Waterman, M.: Introduction to Computational Biology. Addison-Wesley, Reading (1995)MATH
Metadaten
Titel
Avoiding cross-bifix-free binary words
verfasst von
Stefano Bilotta
Elisabetta Grazzini
Elisa Pergola
Renzo Pinzani
Publikationsdatum
01.05.2013
Verlag
Springer-Verlag
Erschienen in
Acta Informatica / Ausgabe 3/2013
Print ISSN: 0001-5903
Elektronische ISSN: 1432-0525
DOI
https://doi.org/10.1007/s00236-013-0176-4