0000000000164278

AUTHOR

Andrzej Kisielewicz

showing 3 related works from this author

A Fast Algorithm Finding the Shortest Reset Words

2012

In this paper we present a new fast algorithm finding minimal reset words for finite synchronizing automata. The problem is know to be computationally hard, and our algorithm is exponential. Yet, it is faster than the algorithms used so far and it works well in practice. The main idea is to use a bidirectional BFS and radix (Patricia) tries to store and compare resulted subsets. We give both theoretical and practical arguments showing that the branching factor is reduced efficiently. As a practical test we perform an experimental study of the length of the shortest reset word for random automata with $n$ states and 2 input letters. We follow Skvorsov and Tipikin, who have performed such a s…

FOS: Computer and information sciencesFormal Languages and Automata Theory (cs.FL)Computer Science - Data Structures and AlgorithmsData Structures and Algorithms (cs.DS)Computer Science - Formal Languages and Automata TheoryComputer Science::Formal Languages and Automata Theory
researchProduct

The Polish School of Argumentation: A Manifesto

2014

Building on our diverse research traditions in the study of reasoning, language and communication, the Polish School of Argumentation integrates various disciplines and institutions across Poland in which scholars are dedicated to understanding the phenomenon of the force of argument. Our primary goal is to craft a methodological programme and establish organisational infrastructure: this is the first key step in facilitating and fostering our research movement, which joins people with a common research focus, complementary skills and an enthusiasm to work together. This statement—the Manifesto—lays the foundations for the research programme of the Polish School of Argumentation.

ManifestoLinguistics and LanguageEnthusiasmmedia_common.quotation_subjectForce of argument Trust Reason Cognition Interdisciplinary approach Argument studies in PolandCommunication studiesinformal logicPolitical communicationfallaciesArgumentation theoryCraftPhilosophyargumentationArgumentPhenomenonPedagogySociologymedia_commonArgumentation
researchProduct

A Fast Algorithm Finding the Shortest Reset Words

2013

In this paper we present a new fast algorithm for finding minimal reset words for finite synchronizing automata, which is a problem appearing in many practical applications. The problem is known to be computationally hard, so our algorithm is exponential in the worst case, but it is faster than the algorithms used so far and it performs well on average. The main idea is to use a bidirectional BFS and radix (Patricia) tries to store and compare subsets. Also a number of heuristics are applied. We give both theoretical and practical arguments showing that the effective branching factor is considerably reduced. As a practical test we perform an experimental study of the length of the shortest …

Computer scienceBranching factorSynchronizing wordApproxHeuristicsReset (computing)AlgorithmComputer Science::Formal Languages and Automata TheoryWord (computer architecture)AutomatonExponential function
researchProduct