Author name cluster

Kai Salomaa

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

54 papers

2 author rows

I&C Journal 2025 Journal Article

Existential and universal width of alternating finite automata

Yo-Sub Han
Sungmin Kim
Sang-Ki Ko
Kai Salomaa

The existential width of an alternating finite automaton (AFA) A on a string w is, roughly speaking, the number of nondeterministic choices that A uses in an accepting computation on w that uses least nondeterminism. The universal width of A on string w is the least number of parallel branches an accepting computation of A on w needs to have. The existential or universal width of A is said to be finite if it is bounded for all accepted strings. We show that finiteness of existential and universal width of an AFA is decidable and at least PSPACE-hard. We consider the problem of deciding whether the existential or universal width is bounded by a given integer. We show that the problem is PSPACE-complete for AFAs where the number of transitions defined for a given universal state and input symbol is bounded by a constant.

TCS Journal 2025 Journal Article

Maximal universal width of an AFA is NP-hard

John Alajaji
Kai Salomaa

The maximal universal width of an alternating finite automaton (AFA) is the largest number parallel computations the machine can have. It is known that deciding finiteness of maximal universal width can be done in polynomial time. We show that deciding whether the maximal universal width of an AFA is greater than a given integer is NP-hard. The proof uses a reduction from the NP-hard membership problem of tabled 0L systems (J. van Leeuwen, 1975).

TCS Journal 2024 Journal Article

Converting finite width AFAs to nondeterministic and universal finite automata

Mohammad Zakzok
Kai Salomaa

The maximal existential (respectively, universal) width of an alternating finite automaton (AFA) on a string w is the maximal number of existential choices encountered in one branch (respectively, the maximal number of universal parallel branches) of a computation of A on w. We give upper bounds for the size of a nondeterministic finite automaton simulating an AFA of finite maximal universal width and for the size of a universal finite automaton simulating an AFA of finite maximal existential width. We give lower bounds for the transformations that are tight within a multiplicative factor that depends only on the universal (respectively, existential) width of the AFA.

TCS Journal 2023 Journal Article

Deciding path size of nondeterministic (and input-driven) pushdown automata

Yo-Sub Han
Sang-Ki Ko
Kai Salomaa

The degree of ambiguity (respectively, the path size) of a nondeterministic automaton, on a given input, measures the number of accepting computations (respectively, the number of all computations). It is known that deciding the finiteness of the degree of ambiguity of a nondeterministic pushdown automaton is undecidable. Also, it is undecidable for a given k ≥ 3 to decide whether the path size of a nondeterministic pushdown automaton is bounded by k. As the main result, we show that deciding the finiteness of the path size of a nondeterministic pushdown automaton can be done in polynomial time. Also, we show that the k-path problem for nondeterministic input-driven pushdown automata (respectively, for nondeterministic finite automata) is complete for exponential time (respectively, complete for polynomial space).

TCS Journal 2023 Journal Article

On Simon's congruence closure of a string

Sungmin Kim
Yo-Sub Han
Sang-Ki Ko
Kai Salomaa

Two strings are Simon's ∼ k -congruent if they have the same set of subsequences of length at most k. We study Simon's congruence closure of a string, which is regular by definition. Given a string w over an alphabet Σ, we present two efficient DFA constructions that accept all ∼ k -congruent strings with respect to w. We also present lower bounds for the state complexity of Simon's congruence closure. Then, we design a polynomial-time algorithm that answers the following open problem: “given a string w over a fixed-sized alphabet, an integer k and a (regular or context-free) language L, decide whether or not there exists a string v ∈ L such that w ∼ k v. ” In addition, for a variable-sized alphabet, we prove that the problem is NP-complete.

TCS Journal 2023 Journal Article

The nondeterministic state complexity of the site-directed deletion language operation

Oliver A.S. Lyon
Kai Salomaa

Site-directed deletion is a language operation inspired by the laboratory procedures entailed by polymerase chain reaction. Site-directed deletion contextually removes a contiguous substring provided it matches a guiding template string. The matching template must match the non-empty prefix and suffix of the substring, where upon the middle section not contained in the outfix is deleted. We consider the nondeterministic state complexity of site-directed deletion over the general alphabet as well as several special restricted forms. For regular languages recognized by nondeterministic finite automata with N and M states, respectively, we establish a new upper bound of 2 N M + N and a new worst case lower bound of 2 N M. The upper bound improves a previously established upper bound, and no non-trivial lower bound was previously known for the nondeterministic state complexity of site-directed deletion.

I&C Journal 2022 Journal Article

Structural properties of NFAs and growth rates of nondeterminism measures

Casey Keeler
Kai Salomaa

Tree width (respectively, string path width) measures the number of partial (respectively, complete) computations of a nondeterministic finite automaton (NFA) on a given input. We characterize polynomial and exponential growth rates of tree width and string path width by structural properties of NFAs. Polynomial growth rates, roughly speaking, require that there exist computations going through a bounded number of cycles where the strings of characters labeling the cycles satisfy certain requirements. As the main result we show that the degrees of the polynomials bounding the tree width and string path width of an NFA differ from each other by at most one. More generally, an NFA is said to have cycle height K if any computation can visit at most K distinct cycles. We give a polynomial time algorithm to decide whether an NFA has finite cycle height and, in the positive case, to compute its optimal cycle height.

TCS Journal 2021 Journal Article

Closest substring problems for regular languages

Yo-Sub Han
Sang-Ki Ko
Timothy Ng
Kai Salomaa

The Closest Substring problem asks whether there exists a consensus string w of given length ℓ such that each string in a set of strings L has a substring whose edit distance is at most r (called the radius) from w. The Closest Substring problem has been studied for finite sets of strings and is known to be NP-hard. We show that the Closest Substring problem for regular languages represented by nondeterministic finite automata (NFA) is PSPACE-complete. The problem remains PSPACE-hard even when the input is a deterministic finite automaton and the length ℓ and radius r are given in unary. Also we show that the Closest Substring problem for acyclic NFAs lies in the second level of the polynomial-time hierarchy and is both NP-hard and coNP-hard.

I&C Journal 2021 Journal Article

Consensus string problem for multiple regular languages

Yo-Sub Han
Sang-Ki Ko
Timothy Ng
Kai Salomaa

The consensus string (or centre string, closest string) of a set S of strings is defined as a string which is within a radius r from all strings in S. We study the consensus string problem for multiple languages recognized by finite automata (FAs). We define the consensus string of languages to be within distance at most r to some string in each of the languages. We also study the decidability and computational complexity of the consensus string problem for multiple formal language instances. We show that the consensus string problem for multiple regular languages is PSPACE -complete even when the radius r is fixed. We prove that the problem can be solved in polynomial time when the number of languages is fixed. Finally, we study that the consensus string problem for the class of input-driven languages and show that the problem is decidable.

TCS Journal 2021 Journal Article

Decision problems and projection languages for restricted variants of two-dimensional automata

Taylor J. Smith
Kai Salomaa

A two-dimensional automaton has a read-only input head that moves in four directions on a finite array of cells labeled by symbols of the input alphabet. A three-way two-dimensional automaton is prohibited from making upward moves, while a two-way two-dimensional automaton can only move downward and rightward. We show that the language emptiness problem for unary three-way nondeterministic two-dimensional automata is NP-complete, and is in P for general-alphabet two-way nondeterministic two-dimensional automata. We also show that the language equivalence and inclusion problems for two-way deterministic two-dimensional automata are decidable, while the language universality, equivalence, and inclusion problems for two-way nondeterministic two-dimensional automata are undecidable. The deterministic case is the first known positive decidability result for a language equivalence problem on two-dimensional automata over a general alphabet. Finally, we discuss the notion of row and column projection languages. We show that the row projection language of a unary three-way nondeterministic two-dimensional automaton is always regular, and that there exists a unary three-way deterministic two-dimensional automaton with a nonregular column projection language. For two-way nondeterministic two-dimensional automata, on the other hand, both the row and column projection languages are always regular.

TCS Journal 2019 Journal Article

Edit distance neighbourhoods of input-driven pushdown automata

Alexander Okhotin
Kai Salomaa

Edit distance ℓ-neighbourhood of a formal language is the set of all strings that can be transformed to one of the strings in this language by at most ℓ insertions and deletions. Both the regular and the context-free languages are known to be closed under this operation, whereas the family recognized by deterministic pushdown automata is not. This paper establishes the closure of the family recognized by input-driven pushdown automata (IDPDA), also known as visibly pushdown automata, under the edit distance neighbourhood operation. For an n-state nondeterministic IDPDA with n stack symbols, an automaton for its edit distance ℓ-neighbourhood using O ( n ℓ + 1 ) states is constructed, and an asymptotically matching lower bound is established. For an n-state deterministic IDPDA, its 1-neighbourhood in the worst case requires a deterministic IDPDA with at least 2 Ω ( n 2 ) states.

TCS Journal 2019 Journal Article

Further closure properties of input-driven pushdown automata

Alexander Okhotin
Kai Salomaa

The paper investigates the closure of the language family defined by input-driven pushdown automata (IDPDA) under the following operations: insertion ins ( L, K ) = { x y z | x z ∈ L, y ∈ K }, deletion del ( L, K ) = { x z | x y z ∈ L, y ∈ K }, square root L = { w | w w ∈ L }, the first half 1 2 L = { u | ∃ v: | u | = | v |, u v ∈ L } and cyclic shift Image 1. For K and L recognized by nondeterministic IDPDA, with m and with n states, respectively, insertion requires exactly m n + 2 m states, as long as K is well-nested; deletion requires exactly 2n states, for well-nested K; square root requires n 3 − O ( n 2 ) states, for well-nested L; the well-nested subset of the first half is representable with 2 O ( n 2 ) states; the well-nested subset of the cyclic shift requires exactly 2 n 2 states. Without the well-nestedness constraints, non-closure is established in each case.

TCS Journal 2019 Journal Article

Site-directed insertion: Language equations and decision problems

Da-Jung Cho
Yo-Sub Han
Kai Salomaa
Taylor J. Smith

Site-directed insertion is an overlapping insertion operation that can be viewed as analogous to the overlap assembly or chop operations that concatenate strings by overlapping a suffix and a prefix of the argument strings. We consider decision problems and language equations involving site-directed insertion. By relying on the tools provided by semantic shuffle on trajectories (M. Domaratzki, Developments in Language Theory 2004) we show that one variable equations involving site-directed insertion and regular constants can be solved algorithmically. We consider also maximal and minimal variants of the site-directed insertion operation and the nondeterministic state complexity of site-directed insertion.

TCS Journal 2017 Journal Article

Outfix-guided insertion

Da-Jung Cho
Yo-Sub Han
Timothy Ng
Kai Salomaa

Motivated by work on bio-operations on DNA strings, we consider an outfix-guided insertion operation that can be viewed as a generalization of the overlap assembly operation on strings studied previously. As the main result we construct a finite language L such that the outfix-guided insertion closure of L is non-regular. We consider also the closure properties of regular and (deterministic) context-free languages under the outfix-guided insertion operation and decision problems related to outfix-guided insertion. Deciding whether a language recognized by a deterministic finite automaton is closed under outfix-guided insertion can be done in polynomial time. The complexity of the corresponding question for nondeterministic finite automata remains open.

TCS Journal 2017 Journal Article

Pseudoknot-generating operation

Da-Jung Cho
Yo-Sub Han
Timothy Ng
Kai Salomaa

A pseudoknot is a crucial intra-molecular structure formed primarily in RNA strands and closely related to important biological processes. This motivates us to define an operation that generates all pseudoknots from a given sequence and consider algorithmic and language theoretic properties of the operation. We design an efficient algorithm that decides whether or not a given string is a pseudoknot of a regular language L. Our algorithm runs in linear time if L is given by a deterministic finite automaton. We study closure and decision properties of the pseudoknot-generating operation. For DNA encoding applications, pseudoknot structures are undesirable. We give polynomial-time algorithms that check whether or not a regular language L contains a pseudoknot or a pseudoknot generated by some string of L. Furthermore, we show that the corresponding questions for context-free languages are undecidable.

TCS Journal 2017 Journal Article

State complexity of permutation on finite languages over a binary alphabet

Da-Jung Cho
Daniel Goč
Yo-Sub Han
Sang-Ki Ko
Alexandros Palioudakis
Kai Salomaa

The set of all strings Parikh equivalent to a string in a language L is called the permutation of L. The permutation of a finite n-state DFA (deterministic finite automaton) language over a binary alphabet can be recognized by a DFA with n 2 − n + 2 2 states. We show that if the language consists of equal length binary strings the bound can be improved to f ( n ) = n 2 + n + 1 3 and for every n congruent to 1 modulo 3 there exists an n-state DFA A recognizing a set of equal length strings such that the minimal DFA for the permutation of L ( A ) needs f ( n ) states.

TCS Journal 2017 Journal Article

State complexity of prefix distance

Timothy Ng
David Rappaport
Kai Salomaa

The prefix distance between strings x and y is the number of symbol occurrences in the strings that do not belong to the longest common prefix of x and y. The suffix and the substring distances are defined analogously in terms of the longest common suffix and longest common substring, respectively, of two strings. We show that the set of strings within prefix distance k from an n state DFA (deterministic finite automaton) language can be recognized by a DFA with ( k + 1 ) ⋅ n − k ( k + 1 ) 2 states and that this number of states is needed in the worst case. Also we give tight bounds for the nondeterministic state complexity of the set of strings within prefix, suffix or substring distance k from a regular language.

I&C Journal 2016 Journal Article

Approximate matching between a context-free grammar and a finite-state automaton

Sang-Ki Ko
Yo-Sub Han
Kai Salomaa

For a given context-free grammar (CFG) and a finite-state automaton (FA), we tackle the edit-distance problem—the problem of computing the most similar pair of strings in the two respective languages. In particular, we consider three different gap cost models for the edit-distance that are crucial for finding a proper alignment between two bio sequences: the linear, affine and concave models. We design efficient algorithms for the edit-distance between a CFG and an FA under these gap cost models. The time complexity of our algorithm for computing the linear or affine gap distance is polynomial and the time complexity for the concave gap distance is exponential.

TCS Journal 2016 Journal Article

Operational state complexity of unary NFAs with finite nondeterminism

Alexandros Palioudakis
Kai Salomaa
Selim G. Akl

We study the state complexity of language operations for unary NFAs with limited nondeterminism. We consider the Boolean operations, concatenation, and Kleene star. We give upper bounds for the state complexity of these language operations and lower bounds that are fairly close to the upper bounds. Our constructions rely on the fact that minimal unary NFAs with limited nondeterminism can be found in Chrobak normal form for most measures of nondeterminism. The measures of nondeterminism which are considered here with the above property are tree width, advice, and trace.

TCS Journal 2016 Journal Article

State complexity of inversion operations

Da-Jung Cho
Yo-Sub Han
Sang-Ki Ko
Kai Salomaa

The reversal operation is well-studied in the literature and the deterministic (respectively, nondeterministic) state complexity of reversal is known to be 2 n (respectively, n). We consider the inversion operation where some substring of the given string is reversed. Formally, the inversion (respectively, prefix-inversion) of a language L consists of all strings u x R v such that u x v ∈ L (respectively, all strings u R x where u x ∈ L ). We show that the nondeterministic state complexity of prefix-inversion is Θ ( n 2 ) and that of inversion is Θ ( n 3 ). We show that the deterministic state complexity of prefix-inversion is at most 2 n ⋅ log ⁡ n + n and has lower bound 2 Ω ( n log ⁡ n ). The same lower bound holds for the state complexity of inversion, but for inversion we do not have a matching upper bound. We also study the state complexity of other variants of the inversion operation.

TCS Journal 2015 Journal Article

Descriptional complexity of unambiguous input-driven pushdown automata

Alexander Okhotin
Kai Salomaa

It is known that a nondeterministic input-driven pushdown automaton (IDPDA) (a. k. a. visibly pushdown automaton; a. k. a. nested word automaton) with n states can be transformed to an equivalent deterministic automaton with 2 Θ ( n 2 ) states (B. von Braunmühl and R. Verbeek, 1983 [8]), and that this size is necessary in the worst case (R. Alur and P. Madhusudan, 2009 [4]). This paper demonstrates that the same worst-case 2 Θ ( n 2 ) size blow-up occurs when converting a nondeterministic IDPDA to an unambiguous one, and an unambiguous IDPDA to a deterministic one. In addition, the methods developed in this paper are used to demonstrate that the descriptional complexity of complementation for nondeterministic IDPDAs is 2 Θ ( n 2 ), and that the descriptional complexity of homomorphisms for deterministic IDPDAs is 2 Θ ( n 2 ).

TCS Journal 2012 Journal Article

Lower bounds for the size of deterministic unranked tree automata

Xiaoxue Piao
Kai Salomaa

Tree automata operating on unranked trees use regular languages, called horizontal languages, to define the transitions of the vertical states that define the bottom-up computation of the automaton. It is well known that the deterministic tree automaton with smallest total number of states, that is, number of vertical states and number of states used to define the horizontal languages, is not unique and it is hard to establish lower bounds for the total number of states. By relying on existing bounds for the size of unambiguous finite automata, we give a lower bound for the size blow-up of determinizing a nondeterministic unranked tree automaton. The lower bound improves the earlier known lower bound that was based on an ad hoc construction.

TCS Journal 2012 Journal Article

State complexity of the concatenation of regular tree languages

Xiaoxue Piao
Kai Salomaa

We consider the state complexity of basic concatenation operations for regular tree languages. We show that the sequential (respectively, parallel) concatenation of tree languages recognized by deterministic bottom-up automata with m and n states can be recognized by an automaton with ( n + 1 ) ⋅ ( m ⋅ 2 n + 2 n − 1 ) − 1 (respectively, m ⋅ 2 n + 2 n − 1 − 1 ) states, and establish matching state complexity lower bounds. The bound for sequential concatenation of tree languages differs by an order of magnitude from the corresponding bound for regular string languages.

TCS Journal 2011 Journal Article

Finite state complexity

Cristian S. Calude
Kai Salomaa
Tania K. Roblot

In this paper we develop a version of Algorithmic Information Theory (AIT) based on finite transducers instead of Turing machines; the complexity induced is called finite-state complexity. In spite of the fact that the Universality Theorem (true for Turing machines) is false for finite transducers, the Invariance Theorem holds true for finite-state complexity. We construct a class of finite-state complexities based on various enumerations of the set of finite transducers. In contrast with descriptional complexities (plain, prefix-free) from AIT, finite-state complexity is computable and there is no a priori upper bound for the number of states used for minimal descriptions of arbitrary strings. Upper and lower bounds for the finite-state complexity of arbitrary strings, and for strings of particular types, are given and incompressible strings are studied.

I&C Journal 2011 Journal Article

Limitations of lower bound methods for deterministic nested word automata

Kai Salomaa

Finite automata operating on nested words were introduced by Alur and Madhusudan in 2006. While nested word automata retain many of the desirable properties of ordinary finite automata, there is no known efficient minimization algorithm for deterministic nested word automata and, interestingly, state complexity bounds for nested word automata turn out to differ significantly from the corresponding bounds for ordinary finite automata. Consequently lower bounds for the state complexity of nested word languages need to rely on fooling set type techniques. We discuss limitations of the techniques and show that, even in the deterministic case, the bounds given by the lower bound methods may be arbitrarily far away from the actual state complexity of the nested word language.

MFCS Conference 2011 Conference Paper

State Complexity of Operations on Input-Driven Pushdown Automata

Alexander Okhotin
Kai Salomaa

Abstract The family of deterministic input-driven pushdown automata (IDPDA; a. k. a. visibly pushdown automata, a. k. a. nested word automata) is known to be closed under reversal, concatenation and Kleene star. As shown by Alur and Madhusudan ( ``Visibly pushdown languages'', STOC 2004), the reversal and the Kleene star of an n -state IDPDA can be represented by an IDPDA with \(2^{O(n^2)}\) states, while concatenation of an m -state and an n -state IDPDA is represented by an IDPDA with \(2^{O((m+n)^2)}\) states. This paper presents more efficient constructions for the reversal and for the Kleene star, which yield 2 Θ( n log n ) states, as well as an m 2 Θ( n log n ) -state construction for the concatenation. These constructions are optimal due to the previously known matching lower bounds.

TCS Journal 2010 Journal Article

Analysis of a cellular automaton model for car traffic with a slow-to-stop rule

Adam Clarridge
Kai Salomaa

We propose a modification of the widely known Benjamin–Johnson–Hui (BJH) cellular automaton model for single-lane traffic simulation. In particular, our model includes a ‘slow-to-stop’ rule that exhibits more realistic microscopic driver behaviour than the BJH model. We present some statistics related to fuel economy and pollution generation and show that our model differs greatly in these measures. We give concise results based on extensive simulations using our system.

TCS Journal 2009 Journal Article

Deciding determinism of caterpillar expressions

Kai Salomaa
Sheng Yu
Jinfeng Zan

Caterpillar expressions have been introduced by Brüggemann-Klein and Wood for applications in markup languages. Caterpillar expressions provide a convenient formalism for specifying the operation of tree-walking automata on unranked trees. Here we give a formal definition of determinism of caterpillar expressions that is based on the language of instruction sequences defined by the expression. We show that determinism of caterpillar expressions can be decided in polynomial time.

TCS Journal 2009 Journal Article

Nondeterministic state complexity of nested word automata

Yo-Sub Han
Kai Salomaa

We study the nondeterministic state complexity of Boolean operations on regular languages of nested words. For union and intersection we obtain matching upper and lower bounds. For complementation of a nondeterministic nested word automaton with n states we establish a lower bound Ω ( n! ) that is significantly worse than the exponential lower bound for ordinary nondeterministic finite automata (NFA). We develop techniques to prove lower bounds for the size of nondeterministic nested word automata that extend the known techniques used for NFAs.

TCS Journal 2009 Journal Article

On the descriptional complexity of Watson–Crick automata

Elena Czeizler
Eugen Czeizler
Lila Kari
Kai Salomaa

Watson–Crick automata are finite state automata working on double-stranded tapes, introduced to investigate the potential of DNA molecules for computing. In this paper, we continue the investigation of descriptional complexity of Watson–Crick automata initiated by Păun et al. [A. Păun, M. Păun, State and transition complexity of Watson–Crick finite automata, in: G. Ciobanu, G. Paun (Eds.), Fundamentals of Computation Theory, FCT’99, in: LNCS, vol. 1684, 1999, pp. 409–420]. In particular, we show that any finite language, as well as any unary regular language, can be recognized by a Watson–Crick automaton with only two, and respectively three, states. Also, we formally define the notion of determinism for these systems. Contrary to the case of non-deterministic Watson–Crick automata, we show that, for deterministic ones, the complementarity relation plays a major role in the acceptance power of these systems.

TCS Journal 2009 Journal Article

On the synchronized derivation depth of context-free grammars

Franziska Biegler
Kai Salomaa

We consider depth of derivations as a complexity measure for synchronized and ordinary context-free grammars. This measure differs from the earlier considered synchronization depth in that it counts the depth of the entire derivation tree. We consider (non-)existence of trade-offs when using synchronized grammars as opposed to non-synchronized grammars and establish lower bounds for certain classes of linear context-free languages.

TCS Journal 2009 Journal Article

Operational state complexity of nested word automata

Xiaoxue Piao
Kai Salomaa

We introduce techniques to prove lower bounds for the number of states needed by finite automata operating on nested words. We study the state complexity of Boolean operations and obtain lower bounds that are tight within an additive constant. The results for union and complementation differ from corresponding bounds for ordinary finite automata. For reversal and concatenation, we establish lower bounds that are of a different order than the worst-case bounds for ordinary finite automata.

TCS Journal 2009 Journal Article

State complexity of basic operations on suffix-free regular languages

Yo-Sub Han
Kai Salomaa

We investigate the state complexity of basic operations for suffix-free regular languages. The state complexity of an operation for regular languages is the number of states that are necessary and sufficient in the worst-case for the minimal deterministic finite-state automaton that accepts the language obtained from the operation. We establish the precise state complexity of catenation, Kleene star, reversal and the Boolean operations for suffix-free regular languages.

I&C Journal 2009 Journal Article

Variants of codes and indecomposable languages

Arto Salomaa
Kai Salomaa
Sheng Yu

We continue the investigation of representing a language as a catenation of languages, each of which cannot be further decomposed in a nontrivial fashion. We study such prime decompositions, both finite and infinite ones. The notion of a length code, an extension of the notion of a code leads to general results concerning decompositions of star languages. Special emphasis is on the decomposition of regular languages. Also some open problems are mentioned.

TCS Journal 2007 Journal Article

An infinite hierarchy induced by depth synchronization

Franziska Biegler
Ian McQuillan
Kai Salomaa

Depth-synchronization measures the number of parallel derivation steps in a synchronized context-free (SCF) grammar. When not bounded by a constant the depth-synchronization measure of an SCF grammar is at least logarithmic and at most linear with respect to the word length. Languages with linear depth-synchronization measure and languages with a depth-synchronization measure in between logarithmic and linear are proven to exist. This gives rise to a strict infinite hierarchy within the family of SCF (and ET0L) languages.

TCS Journal 2007 Journal Article

On the existence of prime decompositions

Yo-Sub Han
Arto Salomaa
Kai Salomaa
Derick Wood
Sheng Yu

We investigate factorizations of regular languages in terms of prime languages. A language is said to be strongly prime decomposable if any way of factorizing it yields a prime decomposition in a finite number of steps. We give a characterization of the strongly prime decomposable regular languages and using the characterization we show that every regular language over a unary alphabet has a prime decomposition. We show that there exist non-regular unary languages that do not have prime decompositions. We also consider infinite factorizations of unary languages.

TCS Journal 2007 Journal Article

On the existence of regular approximations

Brendan Cordy
Kai Salomaa

We approximate context-free, or more general, languages using finite automata. The degree of approximation is measured, roughly speaking, by counting the number of incorrect answers an automaton gives on inputs of length m and observing how these values behave for large m. More restrictive variants are obtained by requiring that the automaton never accepts words outside the language or that it accepts all words in the language. A further distinction is whether a given (context-free) language has a regular approximation which is optimal under the measure of approximation degree or an approximation which is arbitrarily close to optimal. We study closure and decision properties of the approximation measure.

MFCS Conference 2007 Conference Paper

State Complexity of Basic Operations on Suffix-Free Regular Languages

Yo-Sub Han
Kai Salomaa

Abstract We investigate the state complexity of basic operations for suffix-free regular languages. The state complexity of an operation for regular languages is the number of states that are necessary and sufficient in the worst-case for the minimal deterministic finite-state automaton that accepts the language obtained from the operation. We establish the precise state complexity of catenation, Kleene star, reversal and the Boolean operations for suffix-free regular languages.

TCS Journal 2007 Journal Article

State complexity of combined operations

Arto Salomaa
Kai Salomaa
Sheng Yu

We study the state complexity of combined operations. Two particular combined operations are studied: star of union and star of intersection. It is shown that the state complexity of a combined operation is not necessarily similar to the combination of the individual state complexities of the participating operations.

TCS Journal 2007 Journal Article

Transition complexity of language operations

Michael Domaratzki
Kai Salomaa

The number of transitions required by a nondeterministic finite automaton (NFA) to accept a regular language is a natural measure of the size of that language. There has been a significant amount of work related to the trade-off between the number of transitions and other descriptional complexity measures for regular languages. In this paper, we consider the effect of language operations on the number of transitions required to accept a regular language. This work extends previous work on descriptional complexity of regular language operations, in particular, under the measures of deterministic state complexity, nondeterministic state complexity and regular expression size.

TCS Journal 2006 Journal Article

Codes defined by multiple sets of trajectories

Michael Domaratzki
Kai Salomaa

We investigate the use of shuffle on trajectories to model certain classes of languages arising in the theory of codes. In particular, for each finite set of sets of trajectories, which we call a hyperset of trajectories, we define a class of languages induced by that hyperset of trajectories. We investigate the properties of hypersets of trajectories and the associated classes of languages, including the problem of decidability of membership and the problem of equivalence of hypersets of trajectories.

MFCS Conference 2006 Conference Paper

Lower Bounds for the Transition Complexity of NFAs

Michael Domaratzki
Kai Salomaa

Abstract We construct regular languages L n, n ≥1, such that any NFA recognizing L n needs \(\Omega( {\rm nsc}(L_n) \cdot \sqrt{{\rm nsc}(L_n)})\) transitions where nsc( L n ) is the nondeterministic state complexity of L n. Also, we study trade-offs between the number of states and the number of transitions of an NFA. We show that adding one additional state can result in significant reductions in the number of transitions and that there exist regular languages L n, n ≥2, where the transition minimal NFA for L n has more than c nsc( L n ) states, for some constant c > 1.

TCS Journal 2005 Journal Article

Decidability of trajectory-based equations

Michael Domaratzki
Kai Salomaa

We consider the decidability of existence of solutions to language equations involving the operations of shuffle and deletion along trajectories. These operations generalize the operations of catenation, insertion, shuffle, quotient, sequential and scattered deletion, as well as many others. Our results are constructive in the sense that if a solution exists, it can be effectively represented. We show both positive and negative decidability results. We also briefly consider systems of language equations.

MFCS Conference 2004 Conference Paper

Decidability of Trajectory-Based Equations

Michael Domaratzki
Kai Salomaa

Abstract We consider the decidability of existence of solutions to language equations involving the operations of shuffle and deletion along trajectories. These operations generalize the operations of catenation, insertion, shuffle, quotient, sequential and scattered deletion, as well as many others. Our results are constructive in the sense that if a solution exists, it can be effectively represented. We show both positive and negative decidability results.

TCS Journal 2002 Journal Article

Decidability of EDT0L structural equivalence

Kai Salomaa
Sheng Yu

We show that a tree pushdown automaton can verify, for an arbitrary nondeterministically constructed structure tree t, that t does not correspond to any valid derivation of a given EDT0L grammar. In this way we reduce the structural equivalence problem for EDT0L grammars to deciding emptiness of the tree language recognized by a tree pushdown automaton, i. e. , to the emptiness problem for context-free tree languages. Thus we establish that structural equivalence for EDT0L grammars can be decided effectively. The result contrasts the known undecidability result for ET0L structural equivalence.

TCS Journal 2000 Journal Article

Alternating finite automata and star-free languages

Kai Salomaa
Sheng Yu

For a given extended regular expression e we construct an equational representation of an alternating finite automaton accepting the language denoted by e. For star-free extended regular expressions the construction yields a loop-free alternating finite automaton. Also the inclusion in the opposite direction holds and, thus, we obtain a new characterization for the class of star-free languages.

TCS Journal 1998 Journal Article

Synchronization expressions with extended join operation

Kai Salomaa
Sheng Yu

Synchronization expressions are high level constructs used for specifying minimal synchronization constraints of parallel processes. Their semantics is defined by the corresponding synchronization language. The original definition of synchronization expressions [12, 13] forces the languages to be closed under rewriting rules that, for instance, do not preserve regularity. Here we propose an extension of the syntactic definition of synchronization expressions, and an appropriate modification of their semantics. The extended definition has the advantage that it allows us to eliminate the less well motivated transformations (rewriting rules) describing properties of synchronization languages. We show that the modified rewriting rules preserve regularity of the languages. Also, we obtain a characterization of finite synchronization languages as the family consisting of languages satisfying the start-termination property and closed under three types of simple rewriting rules.

TCS Journal 1996 Journal Article

Decidability of equivalence for deterministic synchronized tree automata

Kai Salomaa

Synchronized tree automata allow limited communication between computations in independent subtrees of the input. This enables them to verify, for instance, the equality of two unary subtrees of unlimited size. The class of tree languages recognized by synchronized tree automata is strictly included in the context-free tree languages. As our main result we show that equivalence of tree languages recognized by deterministic synchronized tree automata can be effectively decided. This contrasts the earlier undecidability result for the equivalence problem for nondeterministic synchronized tree automata. For our decidability proof we introduce globally deterministic synchronized tree automata. We establish the various inclusion relations between the deterministic, globally deterministic and nondeterministic synchronized tree automata.

TCS Journal 1996 Journal Article

Structural equivalence and ET0L grammars

Kai Salomaa
Derick Wood
Yu Sheng

For a given context-sensitive grammar G we construct ET0L grammars G 1 and G 2 that are structurally equivalent if and only if the language generated by G is empty, which implies that structural equivalence is undecidable for ET0L grammars. In contrast, structural equivalence is decidable for E0L grammars and for extended E0L grammars. In fact, we show that structural equivalence is undecidable for propagating ET0L grammars in which the number of tables is restricted to be at most two. A stronger notion of equivalence that requires the sets of syntax trees to be isomorphic is shown to be decidable for ET0L grammars.

MFCS Conference 1994 Conference Paper

Complexity of E0L Structural Equivalence

Kai Salomaa
Derick Wood
Sheng Yu 0001

Abstract We show that the EOL structural equivalence problem is logspace hard for deterministic exponential time. Also, we show that this question can be solved in linear space by a synchronized alternating Turing machine, and thus establish an exponential space upper bound for its complexity. The equivalence of finite tree automata is shown to be logspace reducible to context-free structural equivalence. The converse reduction is well known and thus context-free structural equivalence is complete for deterministic exponential time.

TCS Journal 1994 Journal Article

Synchronized tree automata

Kai Salomaa

We introduce synchronized tree automata. They are an extension of the usual tree automaton model where computations in independent subtrees of the input have the capability to communicate in a limited way using the synchronization mechanism. The class of tree languages recognized by the nondeterministic synchronized automata is shown to be properly located between the recognizable and the context-free tree languages. We investigate closure properties and decision problems of synchronized tree automata. Equivalence is shown to be undecidable for the nondeterministic synchronized tree automata but decidable for deterministic equality-synchronized automata.

TCS Journal 1994 Journal Article

The state complexities of some basic operations on regular languages

Sheng Yu
Qingyu Zhuang
Kai Salomaa

We consider the state complexities of some basic operations on regular languages. We show that the number of states that is sufficient and necessary in the worst case for a deterministic finite automaton (DFA) to accept the catenation of an m-state DFA language and an n-state DFA language is exactly m2 n − 2 n − 1, for m, n ⩾ 1. The result of 2 n − 1 + 2 n − 2 states is obtained for the star of an n-state DFA language, n1. State complexities for other basic operations and for regular languages over a one-letter alphabet are also studied.

TCS Journal 1991 Journal Article

Decidability of structural equivalence of E0L grammars

Kai Salomaa
Sheng Yu

We introduce height-counting tree automata that are able to recognize the syntax trees of E0L grammars. The equivalence problem of height-counting tree automata is shown to be decidable and using this result we solve an open problem raised by Ottmann and Wood [5, 6], i. e. , the decidability of structural equivalence of E0L grammars.

TCS Journal 1988 Journal Article

A pumping result for 2-context-free languages

Kai Salomaa

Languages that are generated by context-free grammars in k-parallel derivations (i. e. , at each step exactly k nonterminals, k ⩾ 1, are rewritten) are called k-context-free languages. Here, using the scheduling theory approach as introduced by Gonczarowski and Warmuth (1985), we prove a pumping property of 2-context-free languages. As an application of this result, we show that the hierarchy of k-context-free languages is strict up to level three.