BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Kai Salomaa

Kai Salomaa contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
Formal Languages and Automata Theory

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author
7works
0followers
1topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

7 published item(s)

preprint2020arXiv

Concatenation Operations and Restricted Variants of Two-Dimensional Automata

A two-dimensional automaton operates on arrays of symbols. While a standard (four-way) two-dimensional automaton can move its input head in four directions, restricted two-dimensional automata are only permitted to move their input heads in three or two directions; these models are called three-way and two-way two-dimensional automata, respectively. In two dimensions, we may extend the notion of concatenation in multiple ways, depending on the words to be concatenated. We may row-concatenate (resp., column-concatenate) a pair of two-dimensional words when they have the same number of columns (resp., rows). In addition, the diagonal concatenation operation combines two words at their lower-right and upper-left corners, and is not dimension-dependent. In this paper, we investigate closure properties of restricted models of two-dimensional automata under various concatenation operations. We give non-closure results for two-way two-dimensional automata under row and column concatenation in both the deterministic and nondeterministic cases. We further give positive closure results for the same concatenation operations on unary nondeterministic two-way two-dimensional automata. Finally, we study closure properties of diagonal concatenation on both two- and three-way two-dimensional automata.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Recognition and Complexity Results for Projection Languages of Two-Dimensional Automata

The row projection (resp., column projection) of a two-dimensional language $L$ is the one-dimensional language consisting of all first rows (resp., first columns) of each two-dimensional word in $L$. The operation of row projection has previously been studied under the name "frontier language", and previous work has focused on one- and two-dimensional language classes. In this paper, we study projections of languages recognized by various two-dimensional automaton classes. We show that both the row and column projections of languages recognized by (four-way) two-dimensional automata are exactly context-sensitive. We also show that the column projections of languages recognized by unary three-way two-dimensional automata can be recognized using nondeterministic logspace. Finally, we study the state complexity of projection languages for two-way two-dimensional automata, focusing on the language operations of union and diagonal concatenation.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Finite-State Complexity and the Size of Transducers

Finite-state complexity is a variant of algorithmic information theory obtained by replacing Turing machines with finite transducers. We consider the state-size of transducers needed for minimal descriptions of arbitrary strings and, as our main result, we show that the state-size hierarchy with respect to a standard encoding is infinite. We consider also hierarchies yielded by more general computable encodings.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Nondeterministic State Complexity for Suffix-Free Regular Languages

We investigate the nondeterministic state complexity of basic operations for suffix-free regular languages. The nondeterministic state complexity of an operation is the number of states that are necessary and sufficient in the worst-case for a minimal nondeterministic finite-state automaton that accepts the language obtained from the operation. We consider basic operations (catenation, union, intersection, Kleene star, reversal and complementation) and establish matching upper and lower bounds for each operation. In the case of complementation the upper and lower bounds differ by an additive constant of two.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Operational State Complexity of Deterministic Unranked Tree Automata

We consider the state complexity of basic operations on tree languages recognized by deterministic unranked tree automata. For the operations of union and intersection the upper and lower bounds of both weakly and strongly deterministic tree automata are obtained. For tree concatenation we establish a tight upper bound that is of a different order than the known state complexity of concatenation of regular string languages. We show that (n+1) ( (m+1)2^n-2^(n-1) )-1 vertical states are sufficient, and necessary in the worst case, to recognize the concatenation of tree languages recognized by (strongly or weakly) deterministic automata with, respectively, m and n vertical states.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Transformations Between Different Types of Unranked Bottom-Up Tree Automata

We consider the representational state complexity of unranked tree automata. The bottom-up computation of an unranked tree automaton may be either deterministic or nondeterministic, and further variants arise depending on whether the horizontal string languages defining the transitions are represented by a DFA or an NFA. Also, we consider for unranked tree automata the alternative syntactic definition of determinism introduced by Cristau et al. (FCT'05, Lect. Notes Comput. Sci. 3623, pp. 68-79). We establish upper and lower bounds for the state complexity of conversions between different types of unranked tree automata.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Transition Complexity of Incomplete DFAs

In this paper, we consider the transition complexity of regular languages based on the incomplete deterministic finite automata. A number of results on Boolean operations have been obtained. It is shown that the transition complexity results for union and complementation are very different from the state complexity results for the same operations. However, for intersection, the transition complexity result is similar to that of state complexity.

0 citations0 reviewsNo code linkedOpen access