Recent Submissions

  • State Complexity of Neighbourhoods and Approximate Pattern Matching 

    Ng, Timothy; Rappaport, David; Salomaa, Kai (World Scientific, 2018-02)
    The neighbourhood of a language L with respect to an additive distance consists of all strings that have distance at most the given radius from some string of L. We show that the worst case deterministic state complexity ...
  • Growth Rate of Minimum Branching 

    Palioudakis, Alexandros; Han, Yo-Sub; Salomaa, Kai (Institut fur Informatik, Justus-Liebig Universitat Giessen, 2018-03-14)
    There are different ways of quantifying the nondeterminism used by a nondeterministic finite automaton (NFA). The amount of nondeterminism is measured as a function of the input length. For most ...
  • State complexity of deletion and bipolar deletion 

    Han, Yo-Sub; Ko, Sang-Ki; Salomaa, Kai (Springer-Verlag, 2016)
    It is well known that the language obtained by deleting an arbitrary language from a regular language is regular. We give an upper bound for the state complexity of deleting an arbitrary language from a regular ...
  • Descriptional complexity of unambiguous input-driven pushdown automata 

    Okhotin, Alexander; Salomaa, Kai (Theoretical Computer Science, 2015-04)
    It is known that a nondeterministic input-driven pushdown automaton (IDPDA) (a.k.a.~visibly pushdown automaton; a.k.a.~nested word automaton) of size $n$ can be transformed to an equivalent deterministic automaton of ...
  • Supporting the Model-Driven Development of Real-time Embedded Systems with Run-Time Monitoring and Animation via Highly Customizable Code Generation 

    Das, Nondini; Ganesan, Suchita; Jweda, Leo; Bagherzadeh, Mojtaba; Hili, Nicolas; Dingel, Juergen (ACM, 2016-10-02)
    This paper presents a vision that allows the combined use of model-driven engineering, run-time monitoring, and animation for the development and analysis of components in real-time embedded systems. Key building block in ...
  • Model Development Guidelines for UML-RT: Conventions, Patterns and Antipatterns 

    Das, Tuhin Kanti; Dingel, Juergen (2016-07-21)
    Software development guidelines are a set of rules which can help improve the quality of software. These rules are defined on the basis of experience gained by the software development community over time. This paper ...
  • On a class of covering problems with variable capacities in wireless networks 

    Akl, Selim; Benkoczi, Robert; Gaur, Daya Ram; Hassanein, Hossam; Hossain, Shahadat; Thom, Mark (2016-02-18)
    We consider the problem of allocating clients to base stations in wireless networks. Two design decisions are the location of the base stations, and the power levels of the base stations. We model the interference, due to ...