Collapsing Words: A Progress Report

descriptionPublicationkeyboard_double_arrow_right Part of book or chapter of book , Article , Conference object 01 Jan 2005Publisher:Springer Berlin HeidelbergJournal:International Journal of Foundations of Computer Science, volume 17, pages 507-518 (issn: 0129-0541, eissn: 1793-6373,

Copyright policy )

Authors: Dimitry S. Ananichev; Ilja V. Petrov; Mikhail V. Volkov 0001;

doi: 10.1007/11505877_2 , 10.1142/s0129054106003966

Collapsing Words: A Progress Report

- Summary
- Subjects
- Metrics

Abstract

A word w over a finite alphabet Σ is n-collapsing if for an arbitrary DFA [Formula: see text], the inequality |δ(Q, w)| ≤ |Q| - n holds provided that |δ(Q, u)| ≤ |Q| - n for some word u ∈ Σ+(depending on [Formula: see text]). We overview some recent results related to this notion. One of these results implies that the property of being n-collapsing is algorithmically recognizable for any given positive integer n.

Related Organizations

Ural State Agrarian University
Russian Federation
Ural State Law University
Russian Federation

Keywords

deterministic finite automaton, \(n\)-collapsing word, Formal languages and automata, identity checking problem, \(n\)-compressing word

Impact byBIP!

	selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	7
	popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.	Average
	influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	Top 10%
	impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.	Average