Kai Salomaa

306 papers A* 1B 14C 45Misc 3Journal 158Unranked 84
YearRankTypeTitle / Venue / Authors
2026 — conf
Generalized Welfare-Aware Matching with Multimodal Preferences and Criteria Strategizing of Autonomous Agents.
ICAART (1)
Peash Ranjan Saha, Salimur Choudhury, Kai Salomaa
2025 J jnl
Algorithmic Approach of Majority Voting With Agents' Inclusiveness for Facility Resource Matching.
IEEE Access
Peash Ranjan Saha, Salimur Choudhury, Kai Salomaa
2025 J jnl
Algorithms for maximal existential and universal width.
Nat. Comput.
John Alajaji, Kai Salomaa
2025 J jnl
Existential and universal width of alternating finite automata.
Inf. Comput.
Yo-Sub Han, Sungmin Kim, Sang-Ki Ko, Kai Salomaa
2025 C conf
Improved Upper Bounds for Determinizing NIDPDAs with Limited Nondeterminism.
DLT
Mohammad Zakzok, Kai Salomaa
2025 J jnl
Maximal universal width of an AFA is NP-hard.
Theor. Comput. Sci.
John Alajaji, Kai Salomaa
2025 J jnl
Quantum Long Short-Term Memory-Assisted Optimization for Efficient Vehicle Platooning in Connected and Autonomous Systems.
IEEE Open J. Comput. Soc.
Mahzabeen Emu, Taufiq Rahman, Salimur Choudhury, Kai Salomaa
2025 — conf
Small Balanced Vertex Separators in NFA to Regular Expression Conversion.
DCFS
Derek Youngman, Kai Salomaa
2024 — conf
Altruistic Bandit Learning For One-to-Many Matching Markets.
GoodIT
Peash Ranjan Saha, Salimur Choudhury, Kai Salomaa
2024 J jnl
Converting finite width AFAs to nondeterministic and universal finite automata.
Theor. Comput. Sci.
Mohammad Zakzok, Kai Salomaa
2024 J jnl
Descriptional Complexity of Finite Automata - Selected Highlights.
Fundam. Informaticae
Arto Salomaa, Kai Salomaa, Taylor J. Smith
2024 Misc conf
Next-Generation Vehicle Platooning: Leveraging Quantum Long Short-Term Memory Networks.
QCE
Mahzabeen Emu, Taufiq Rahman, Salimur Choudhury, Kai Salomaa
2024 — conf
Robust Virtual Network Function Optimization Under Post-Failure Uncertainty: Classical & Quantum Computing.
DRCN
Mahzabeen Emu, Salimur Choudhury, Kai Salomaa
2024 J jnl
Special Issue: Articles Dedicated to the Memory of Magnus Steinby - Preface.
Int. J. Found. Comput. Sci.
Zoltán Fülöp, George Rahonis, Kai Salomaa
2024 J jnl
Stochastic Resource Optimization for Metaverse Data Marketplace by Leveraging Quantum Neural Networks.
IEEE Trans. Netw. Serv. Manag.
Mahzabeen Emu, Salimur Choudhury, Kai Salomaa
2024 C conf
Universal Rewriting Rules for the Parikh Matrix Injectivity Problem.
DLT
Ingyu Baek, Joonghyuk Hahn, Yo-Sub Han, Kai Salomaa
2024 J jnl
Warm and Cold Start Quantum Annealing for Metaverse Resource Optimization.
IEEE Open J. Commun. Soc.
Mahzabeen Emu, Salimur Choudhury, Kai Salomaa
2023 — conf
Balancing Matching of Two-Sided Agents with Adaptive and Fair Instability.
SSCI
Peash Ranjan Saha, Salimur Choudhury, Kai Salomaa
2023 J jnl
Deciding path size of nondeterministic (and input-driven) pushdown automata.
Theor. Comput. Sci.
Yo-Sub Han, Sang-Ki Ko, Kai Salomaa
2023 J jnl
Descriptional Complexity of Finite Automata - Selected Highlights.
CoRR
Arto Salomaa, Kai Salomaa, Taylor J. Smith
2023 — conf
Existential and Universal Width of Alternating Finite Automata.
DCFS
Yo-Sub Han, Sungmin Kim, Sang-Ki Ko, Kai Salomaa
2023 J jnl
Maximal Existential and Universal Width.
Sci. Ann. Comput. Sci.
Casey Keeler, Kai Salomaa
2023 C conf
Multi-Objective Task Assignment Solution for Parked Vehicular Computing.
ICORES
Jia He Sun, Salimur Choudhury, Kai Salomaa
2023 J jnl
On Simon's congruence closure of a string.
Theor. Comput. Sci.
Sungmin Kim, Yo-Sub Han, Sang-Ki Ko, Kai Salomaa
2023 C conf
On the Simon's Congruence Neighborhood of Languages.
DLT
Sungmin Kim, Yo-Sub Han, Sang-Ki Ko, Kai Salomaa
2023 — conf
Quantum Computing Empowered Metaverse: An Approach for Resource Optimization.
ICC
Mahzabeen Emu, Salimur Choudhury, Kai Salomaa
2023 B conf
Quantum Neural Networks driven Stochastic Resource Optimization for Metaverse Data Marketplace.
NetSoft
Mahzabeen Emu, Salimur Choudhury, Kai Salomaa
2023 J jnl
Recognition and Complexity Results for Projection Languages of Two-Dimensional Automata.
J. Autom. Lang. Comb.
Taylor J. Smith, Kai Salomaa
2023 J jnl
The nondeterministic state complexity of the site-directed deletion language operation.
Theor. Comput. Sci.
Oliver A. S. Lyon, Kai Salomaa
2022 — conf
A Two-Stage Based Strategy to Optimize Homeless Placement in Shelters.
IHTC
Peash Ranjan Saha, Salimur Choudhury, Kai Salomaa
2022 J jnl
An online fair resource allocation solution for fog computing.
Int. J. Parallel Emergent Distributed Syst.
Jia He Sun, Salimur Choudhury, Kai Salomaa
2022 C conf
Nondeterministic State Complexity of Site-Directed Deletion.
CIAA
Oliver A. S. Lyon, Kai Salomaa
2022 J jnl
Nondeterministic State Complexity of Site-Directed Insertion.
J. Autom. Lang. Comb.
Oliver A. S. Lyon, Kai Salomaa
2022 — conf
On Simon's Congruence Closure of a String.
DCFS
Sungmin Kim, Yo-Sub Han, Sang-Ki Ko, Kai Salomaa
2022 — conf
Resource Optimization of SFC Embedding for IoT Networks Using Quantum Computing.
CAMAD
Mahzabeen Emu, Salimur Choudhury, Kai Salomaa
2022 J jnl
Structural properties of NFAs and growth rates of nondeterminism measures.
Inf. Comput.
Chris Keeler, Kai Salomaa
2021 J jnl
Closest substring problems for regular languages.
Theor. Comput. Sci.
Yo-Sub Han, Sang-Ki Ko, Timothy Ng, Kai Salomaa
2021 B conf
Concatenation Operations and Restricted Variants of Two-Dimensional Automata.
SOFSEM
Taylor J. Smith, Kai Salomaa
2021 J jnl
Consensus string problem for multiple regular languages.
Inf. Comput.
Yo-Sub Han, Sang-Ki Ko, Timothy Ng, Kai Salomaa
2021 J jnl
Decision problems and projection languages for restricted variants of two-dimensional automata.
Theor. Comput. Sci.
Taylor J. Smith, Kai Salomaa
2021 C conf
Degrees of Restriction for Two-Dimensional Automata.
CIAA
Taylor J. Smith, Kai Salomaa
2021 J jnl
Degrees of Restriction for Two-Dimensional Automata.
CoRR
Taylor J. Smith, Kai Salomaa
2021 J jnl
Generalizations of Code Languages with Marginal Errors.
Int. J. Found. Comput. Sci.
Sang-Ki Ko, Yo-Sub Han, Kai Salomaa
2021 — conf
Width Measures of Alternating Finite Automata.
DCFS
Chris Keeler, Kai Salomaa
2020 C conf
Alternating Finite Automata with Limited Universal Branching.
LATA
Chris Keeler, Kai Salomaa
2020 — conf
Combining Limited Parallelism and Nondeterminism in Alternating Finite Automata.
DCFS
Chris Keeler, Kai Salomaa
2020 J jnl
Concatenation Operations and Restricted Variants of Two-Dimensional Automata.
CoRR
Taylor J. Smith, Kai Salomaa
2020 — conf
Recognition and Complexity Results for Projection Languages of Two-Dimensional Automata.
DCFS
Taylor J. Smith, Kai Salomaa
2020 J jnl
Recognition and Complexity Results for Projection Languages of Two-Dimensional Automata.
CoRR
Taylor J. Smith, Kai Salomaa
2019 J jnl
Branching Measures and Nearly Acyclic NFAs.
Int. J. Found. Comput. Sci.
Chris Keeler, Kai Salomaa
2019 C conf
Decision Problems for Restricted Variants of Two-Dimensional Automata.
CIAA
Taylor J. Smith, Kai Salomaa
2019 J jnl
Decision Problems for Restricted Variants of Two-Dimensional Automata.
CoRR
Taylor J. Smith, Kai Salomaa
2019 J jnl
Edit distance neighbourhoods of input-driven pushdown automata.
Theor. Comput. Sci.
Alexander Okhotin, Kai Salomaa
2019 J jnl
Further closure properties of input-driven pushdown automata.
Theor. Comput. Sci.
Alexander Okhotin, Kai Salomaa
2019 J jnl
Improved Recruitment Algorithms for Vehicular Crowdsensing Networks.
IEEE Trans. Veh. Technol.
Fabio Campioni, Salimur Choudhury, Kai Salomaa, Selim G. Akl
2019 — conf
Limited Nondeterminism of Input-Driven Pushdown Automata: Decidability and Complexity.
DCFS
Yo-Sub Han, Sang-Ki Ko, Kai Salomaa
2019 J jnl
Localized algorithms for redundant readers elimination in RFID networks.
Int. J. Parallel Emergent Distributed Syst.
Nafiul Rashid, Salimur Choudhury, Kai Salomaa
2019 — conf
Nondeterminism Growth and State Complexity.
DCFS
Chris Keeler, Kai Salomaa
2019 J jnl
Site-directed insertion: Language equations and decision problems.
Theor. Comput. Sci.
Da-Jung Cho, Yo-Sub Han, Kai Salomaa, Taylor J. Smith
2019 J jnl
State Complexity of Suffix Distance.
Int. J. Found. Comput. Sci.
Timothy Ng, David Rappaport, Kai Salomaa
2019 J jnl
State Complexity of the Quotient Operation on Input-Driven Pushdown Automata.
Int. J. Found. Comput. Sci.
Alexander Okhotin, Kai Salomaa
2019 C conf
The Relative Edit-Distance Between Two Input-Driven Languages.
DLT
Hyunjoon Cheon, Yo-Sub Han, Sang-Ki Ko, Kai Salomaa
2018 C conf
Closest Substring Problems for Regular Languages.
DLT
Yo-Sub Han, Sang-Ki Ko, Timothy Ng, Kai Salomaa
2018 — conf
Cycle Height of Finite Automata.
DCFS
Chris Keeler, Kai Salomaa
2018 — conf
Further Closure Properties of Input-Driven Pushdown Automata.
DCFS
Alexander Okhotin, Kai Salomaa
2018 J jnl
Growth Rate of Minimum Branching.
J. Autom. Lang. Comb.
Alexandros Palioudakis, Yo-Sub Han, Kai Salomaa
2018 J jnl
Routing in a polygonal terrain with the shortest beacon watchtower.
Comput. Geom.
Bahram Kouhestani, David Rappaport, Kai Salomaa
2018 C conf
Site-Directed Deletion.
DLT
Da-Jung Cho, Yo-Sub Han, Hwee Kim, Kai Salomaa
2018 — conf
Site-Directed Insertion: Decision Problems, Maximality and Minimality.
DCFS
Da-Jung Cho, Yo-Sub Han, Kai Salomaa, Taylor J. Smith
2018 J jnl
Site-Directed Insertion: Decision Problems, Maximality and Minimality.
CoRR
Da-Jung Cho, Yo-Sub Han, Kai Salomaa, Taylor J. Smith
2018 J jnl
State Complexity of Neighbourhoods and Approximate Pattern Matching.
Int. J. Found. Comput. Sci.
Timothy Ng, David Rappaport, Kai Salomaa
2017 J jnl
Ambiguity, Nondeterminism and State Complexity of Finite Automata.
Acta Cybern.
Yo-Sub Han, Arto Salomaa, Kai Salomaa
2017 — conf
Branching Measures and Nearly Acyclic NFAs.
DCFS
Chris Keeler, Kai Salomaa
2017 C conf
Consensus String Problem for Multiple Regular Languages.
LATA
Yo-Sub Han, Sang-Ki Ko, Timothy Ng, Kai Salomaa
2017 Misc conf
Edit Distance Neighbourhoods of Input-Driven Pushdown Automata.
CSR
Alexander Okhotin, Kai Salomaa
2017 J jnl
Outfix-guided insertion.
CoRR
Da-Jung Cho, Yo-Sub Han, Timothy Ng, Kai Salomaa
2017 J jnl
Outfix-guided insertion.
Theor. Comput. Sci.
Da-Jung Cho, Yo-Sub Han, Timothy Ng, Kai Salomaa
2017 J jnl
Preface.
Int. J. Found. Comput. Sci.
Yo-Sub Han, Kai Salomaa
2017 J jnl
Pseudoknot-generating operation.
Theor. Comput. Sci.
Da-Jung Cho, Yo-Sub Han, Timothy Ng, Kai Salomaa
2017 — conf
Quasi-Distances and Weighted Finite Automata.
The Role of Theory in Computer Science
Timothy Ng, David Rappaport, Kai Salomaa
2017 C conf
Relative Prefix Distance Between Languages.
DLT
Timothy Ng, David Rappaport, Kai Salomaa
2017 J jnl
Report on the Magic in Science symposium.
Bull. EATCS
Kai Salomaa, Andrew L. Szilard
2017 J jnl
State Complexity of Prefix Distance of Subregular Languages.
J. Autom. Lang. Comb.
Timothy Ng, David Rappaport, Kai Salomaa
2017 — conf
State Complexity of Suffix Distance.
DCFS
Timothy Ng, David Rappaport, Kai Salomaa
2017 J jnl
State Complexity of k-Parallel Tree Concatenation.
Fundam. Informaticae
Yo-Sub Han, Sang-Ki Ko, Kai Salomaa
2017 J jnl
State complexity of operations on input-driven pushdown automata.
J. Comput. Syst. Sci.
Alexander Okhotin, Kai Salomaa
2017 J jnl
State complexity of permutation on finite languages over a binary alphabet.
Theor. Comput. Sci.
Da-Jung Cho, Daniel Goc, Yo-Sub Han, Sang-Ki Ko, Alexandros Palioudakis, Kai Salomaa
2017 J jnl
State complexity of prefix distance.
Theor. Comput. Sci.
Timothy Ng, David Rappaport, Kai Salomaa
2017 — conf
The Quotient Operation on Input-Driven Pushdown Automata.
DCFS
Alexander Okhotin, Kai Salomaa
2017 J jnl
Worst Case Branching and Other Measures of Nondeterminism.
Int. J. Found. Comput. Sci.
Alexandros Palioudakis, Kai Salomaa, Selim G. Akl
2016 J jnl
Approximate matching between a context-free grammar and a finite-state automaton.
Inf. Comput.
Sang-Ki Ko, Yo-Sub Han, Kai Salomaa
2016 — conf
CARRE: Cellular automaton based redundant readers elimination in RFID networks.
ICC
Nafiul Rashid, Salimur Choudhury, Kai Salomaa
2016 J jnl
Duplications and Pseudo-Duplications.
Int. J. Unconv. Comput.
Da-Jung Cho, Yo-Sub Han, Hwee Kim, Alexandros Palioudakis, Kai Salomaa
2016 C ed.
Implementation and Application of Automata - 21st International Conference, CIAA 2016, Seoul, South Korea, July 19-22, 2016, Proceedings
CIAA
Yo-Sub Han, Kai Salomaa
2016 J jnl
Operational state complexity of unary NFAs with finite nondeterminism.
Theor. Comput. Sci.
Alexandros Palioudakis, Kai Salomaa, Selim G. Akl
2016 C conf
Outfix-Guided Insertion - (Extended Abstract).
DLT
Da-Jung Cho, Yo-Sub Han, Timothy Ng, Kai Salomaa
2016 J jnl
Pseudo-inversion: closure properties and decidability.
Nat. Comput.
Da-Jung Cho, Yo-Sub Han, Shin-Dong Kang, Hwee Kim, Sang-Ki Ko, Kai Salomaa
2016 B conf
Pseudoknot-Generating Operation.
SOFSEM
Da-Jung Cho, Yo-Sub Han, Timothy Ng, Kai Salomaa
2016 J jnl
State Complexity of Insertion.
Int. J. Found. Comput. Sci.
Yo-Sub Han, Sang-Ki Ko, Timothy Ng, Kai Salomaa
2016 — conf
State Complexity of Prefix Distance of Subregular Languages.
DCFS
Timothy Ng, David Rappaport, Kai Salomaa
2016 J jnl
State complexity of deletion and bipolar deletion.
Acta Informatica
Yo-Sub Han, Sang-Ki Ko, Kai Salomaa
2016 J jnl
State complexity of inversion operations.
Theor. Comput. Sci.
Da-Jung Cho, Yo-Sub Han, Sang-Ki Ko, Kai Salomaa
2016 — conf
The Length of the Beacon Attraction Trajectory.
CCCG
Bahram Kouhestani, David Rappaport, Kai Salomaa
2015 J jnl
Cellular Automaton Based Localized Algorithms for Mobile Sensor Networks.
Int. J. Unconv. Comput.
Salimur Choudhury, Kai Salomaa, Selim G. Akl
2015 B conf
Cellular automata and object monitoring in mobile wireless sensor networks.
WCNC
Salimur Choudhury, Kai Salomaa, Selim G. Akl
2015 J jnl
Descriptional complexity of unambiguous input-driven pushdown automata.
Theor. Comput. Sci.
Alexander Okhotin, Kai Salomaa
2015 — conf
Duplications and Pseudo-Duplications.
UCNC
Da-Jung Cho, Yo-Sub Han, Hwee Kim, Alexandros Palioudakis, Kai Salomaa
2015 C conf
Generalizations of Code Languages with Marginal Errors.
DLT
Yo-Sub Han, Sang-Ki Ko, Kai Salomaa
2015 — conf
Nondeterministic Tree Width of Regular Languages.
DCFS
Cezar Câmpeanu, Kai Salomaa
2015 — conf
On the Inverse Beacon Attraction Region of a Point.
CCCG
Bahram Kouhestani, David Rappaport, Kai Salomaa
2015 — conf
Quasi-Distances and Weighted Finite Automata.
DCFS
Timothy Ng, David Rappaport, Kai Salomaa
2015 J jnl
State Complexity of
Int. J. Found. Comput. Sci.
Hae-Sung Eom, Yo-Sub Han, Kai Salomaa
2015 J jnl
State Complexity of Kleene-Star Operations on Regular Tree Languages.
Acta Cybern.
Yo-Sub Han, Sang-Ki Ko, Xiaoxue Piao, Kai Salomaa
2015 C conf
State Complexity of Neighbourhoods and Approximate Pattern Matching.
DLT
Timothy Ng, David Rappaport, Kai Salomaa
2015 C conf
State Complexity of Prefix Distance.
CIAA
Timothy Ng, David Rappaport, Kai Salomaa
2015 — conf
The State Complexity of Permutations on Finite Languages over Binary Alphabets.
DCFS
Alexandros Palioudakis, Da-Jung Cho, Daniel Goc, Yo-Sub Han, Sang-Ki Ko, Kai Salomaa
2015 J jnl
Unary NFAs, Limited Nondeterminism, and Chrobak Normal Form.
Int. J. Unconv. Comput.
Alexandros Palioudakis, Kai Salomaa, Selim G. Akl
2014 — conf
Cellular automata and Mobile Wireless Sensor Networks.
CCECE
Salimur Choudhury, Kai Salomaa, Selim G. Akl
2014 J jnl
Cellular automaton-based algorithms for the dispersion of mobile wireless sensor networks.
Int. J. Parallel Emergent Distributed Syst.
Salimur Choudhury, Kai Salomaa, Selim G. Akl
2014 J jnl
Complexity of input-driven pushdown automata.
SIGACT News
Alexander Okhotin, Kai Salomaa
2014 — conf
Computation Width and Deviation Number.
DCFS
Daniel Goc, Kai Salomaa
2014 C conf
Input-Driven Pushdown Automata with Limited Nondeterminism - (Invited Paper).
Developments in Language Theory
Alexander Okhotin, Kai Salomaa
2014 J jnl
Lower Bound for Converting an NFA with Finite Nondeterminism into an MDFA.
J. Autom. Lang. Comb.
Alexandros Palioudakis, Kai Salomaa, Selim G. Akl
2014 J jnl
Nondeterministic State Complexity of Proportional Removals.
Int. J. Found. Comput. Sci.
Daniel Goc, Alexandros Palioudakis, Kai Salomaa
2014 — conf
Pseudo-inversion on Formal Languages.
UCNC
Da-Jung Cho, Yo-Sub Han, Shin-Dong Kang, Hwee Kim, Sang-Ki Ko, Kai Salomaa
2014 — conf
Routing in a Polygonal Terrain with the Shortest Beacon Watchtower.
CCCG
Bahram Kouhestani, David Rappaport, Kai Salomaa
2014 — conf
State Complexity of Combined Operations for Prefix-Free Regular Languages.
Discrete Mathematics and Computer Science
Hae-Sung Eom, Yo-Sub Han, Kai Salomaa, Sheng Yu
2014 C conf
State Complexity of Deletion.
Developments in Language Theory
Yo-Sub Han, Sang-Ki Ko, Kai Salomaa
2014 — conf
State Complexity of Inversion Operations.
DCFS
Da-Jung Cho, Yo-Sub Han, Sang-Ki Ko, Kai Salomaa
2014 — conf
State Complexity of Unary Language Operations for NFAs with Limited Nondeterminism.
DCFS
Alexandros Palioudakis, Kai Salomaa, Selim G. Akl
2014 C conf
Top-Down Tree Edit-Distance of Regular Tree Languages.
LATA
Sang-Ki Ko, Yo-Sub Han, Kai Salomaa
2014 B conf
Unary NFAs with Limited Nondeterminism.
SOFSEM
Alexandros Palioudakis, Kai Salomaa, Selim G. Akl
2013 C conf
Approximate Matching between a Context-Free Grammar and a Finite-State Automaton.
CIAA
Yo-Sub Han, Sang-Ki Ko, Kai Salomaa
2013 — conf
Comparisons between Measures of Nondeterminism on Finite Automata.
DCFS
Alexandros Palioudakis, Kai Salomaa, Selim G. Akl
2013 — conf
Finite Nondeterminism vs. DFAs with Multiple Initial States.
DCFS
Alexandros Palioudakis, Kai Salomaa, Selim G. Akl
2013 J jnl
Goodby to the Kindhearted Dragon Prof. Sheng Yu, 1950-2012.
Int. J. Found. Comput. Sci.
Arto Salomaa, Kai Salomaa, Andrew L. Szilard
2013 — conf
Input-driven pushdown automata: nondeterminism and unambiguity.
NCMA
Alexander Okhotin, Kai Salomaa
2013 — conf
Nondeterministic State Complexity of Proportional Removals.
DCFS
Daniel Goc, Alexandros Palioudakis, Kai Salomaa
2013 — conf
State Complexity of k-Union and k-Intersection for Prefix-Free Regular Languages.
DCFS
Hae-Sung Eom, Yo-Sub Han, Kai Salomaa
2013 J jnl
The Edit-Distance between a Regular Language and a Context-Free Language.
Int. J. Found. Comput. Sci.
Yo-Sub Han, Sang-Ki Ko, Kai Salomaa
2013 J jnl
Undecidability of state complexity.
Int. J. Comput. Math.
Arto Salomaa, Kai Salomaa, Sheng Yu
2012 J jnl
A Cellular Automaton Model for Wireless Sensor Networks.
J. Cell. Autom.
Salimur Choudhury, Kai Salomaa, Selim G. Akl
2012 — conf
A cellular automaton model for connectivity preserving deployment of mobile wireless sensors.
ICC
Salimur Choudhury, Kai Salomaa, Selim G. Akl
2012 — conf
Cellular Automaton Based Motion Planning Algorithms for Mobile Sensor Networks.
TPNC
Salimur Choudhury, Kai Salomaa, Selim G. Akl
2012 — conf
Cellular automaton based algorithms for depth adjustment in underwater mobile sensor networks.
MASS Workshops
Salimur Choudhury, Kai Salomaa, Selim G. Akl
2012 C conf
Computing the Edit-Distance between a Regular Language and a Context-Free Language.
Developments in Language Theory
Yo-Sub Han, Sang-Ki Ko, Kai Salomaa
2012 — conf
Descriptional Complexity of Input-Driven Pushdown Automata.
Languages Alive
Alexander Okhotin, Xiaoxue Piao, Kai Salomaa
2012 B conf
Energy efficient cellular automaton based algorithms for mobile wireless sensor networks.
WCNC
Salimur Choudhury, Selim G. Akl, Kai Salomaa
2012 J jnl
Extended Watson-Crick L systems with regular trigger languages and restricted derivation modes.
Nat. Comput.
David Sears, Kai Salomaa
2012 C conf
In Memoriam Sheng Yu.
CIAA
Yuan Gao, Kai Salomaa
2012 J jnl
Lower bounds for the size of deterministic unranked tree automata.
Theor. Comput. Sci.
Xiaoxue Piao, Kai Salomaa
2012 J jnl
Sheng Yu (1950-2012) In Memoriam.
Fundam. Informaticae
Arto Salomaa, Kai Salomaa, Andrew L. Szilard
2012 — conf
State Complexity and Limited Nondeterminism.
DCFS
Alexandros Palioudakis, Kai Salomaa, Selim G. Akl
2012 J jnl
State Complexity of Finite Tree Width NFAs.
J. Autom. Lang. Comb.
Alexandros Palioudakis, Kai Salomaa, Selim G. Akl
2012 — conf
State Complexity of Kleene-Star Operations on Trees.
Computation, Physics and Beyond
Xiaoxue Piao, Kai Salomaa
2012 — conf
State Complexity of Projection and Quotient on Unranked Trees.
DCFS
Xiaoxue Piao, Kai Salomaa
2012 J jnl
State complexity of the concatenation of regular tree languages.
Theor. Comput. Sci.
Xiaoxue Piao, Kai Salomaa
2012 J jnl
State-Size Hierarchy for Finite-State Complexity.
Int. J. Found. Comput. Sci.
Cristian S. Calude, Kai Salomaa, Tania Roblot
2011 C conf
Descriptional Complexity of Unambiguous Nested Word Automata.
LATA
Alexander Okhotin, Kai Salomaa
2011 J jnl
Editorial: Computing with biomolecules.
Nat. Comput.
Erzsébet Csuhaj-Varjú, Kai Salomaa
2011 C conf
Extended Watson-Crick L Systems with Regular Trigger Languages.
UC
David Sears, Kai Salomaa
2011 J jnl
Finite state complexity.
Theor. Comput. Sci.
Cristian S. Calude, Kai Salomaa, Tania Roblot
2011 C ed.
Implementation and Application of Automata - 15th International Conference, CIAA 2010, Winnipeg, MB, Canada, August 12-15, 2010. Revised Selected Papers
CIAA
Michael Domaratzki, Kai Salomaa
2011 J jnl
Limitations of lower bound methods for deterministic nested word automata.
Inf. Comput.
Kai Salomaa
2011 — conf
On Language Decompositions and Primality.
Rainbow of Computer Science
Michael Domaratzki, Kai Salomaa
2011 J jnl
Overlap-Free Languages and solid Codes.
Int. J. Found. Comput. Sci.
Yo-Sub Han, Kai Salomaa
2011 J jnl
Preface.
Int. J. Found. Comput. Sci.
Michael Domaratzki, Kai Salomaa
2011 B conf
State Complexity of Operations on Input-Driven Pushdown Automata.
MFCS
Alexander Okhotin, Kai Salomaa
2011 — conf
State Trade-Offs in Unranked Tree Automata.
DCFS
Xiaoxue Piao, Kai Salomaa
2011 J jnl
Transformations Between Different Models of Unranked Bottom-Up Tree Automata.
Fundam. Informaticae
Xiaoxue Piao, Kai Salomaa
2011 J jnl
Transition Complexity of Incomplete DFAs.
Fundam. Informaticae
Yuan Gao, Kai Salomaa, Sheng Yu
2011 — conf
Tree Homomorphisms for Unranked Trees.
AFL
Xiaoxue Piao, Kai Salomaa, Sándor Vágvölgyi
2011 C conf
Undecidability of the State Complexity of Composed Regular Operations.
LATA
Arto Salomaa, Kai Salomaa, Sheng Yu
2010 J jnl
An Improved Cellular Automata Based Algorithm for the 45-Convex Hull Problem.
J. Cell. Autom.
Adam Clarridge, Kai Salomaa
2010 J jnl
Analysis of a cellular automaton model for car traffic with a slow-to-stop rule.
Theor. Comput. Sci.
Adam Clarridge, Kai Salomaa
2010 — conf
Finite-State Complexity and the Size of Transducers
DCFS
Cristian Calude, Kai Salomaa, Tania Roblot
2010 — conf
Nondeterministic State Complexity for Suffix-Free Regular Languages
DCFS
Yo-Sub Han, Kai Salomaa
2010 — conf
Operational State Complexity of Deterministic Unranked Tree Automata
DCFS
Xiaoxue Piao, Kai Salomaa
2010 J jnl
Orthogonal Concatenation: Language Equations and State Complexity.
J. Univers. Comput. Sci.
Mark Daley, Michael Domaratzki, Kai Salomaa
2010 — conf
Transformations Between Different Types of Unranked Bottom-Up Tree Automata
DCFS
Xiaoxue Piao, Kai Salomaa
2010 — conf
Transition Complexity of Incomplete DFAs
DCFS
Yuan Gao, Kai Salomaa, Sheng Yu
2009 C conf
A Cellular Automaton Model for Car Traffic with a Slow-to-Stop Rule.
CIAA
Adam Clarridge, Kai Salomaa
2009 C conf
A Cryptosystem Based on the Composition of Reversible Cellular Automata.
LATA
Adam Clarridge, Kai Salomaa
2009 J jnl
Deciding determinism of caterpillar expressions.
Theor. Comput. Sci.
Kai Salomaa, Sheng Yu, Jinfeng Zan
2009 J jnl
Nondeterministic State Complexity of Basic Operations for Prefix-Free Regular Languages.
Fundam. Informaticae
Yo-Sub Han, Kai Salomaa, Derick Wood
2009 J jnl
Nondeterministic state complexity of nested word automata.
Theor. Comput. Sci.
Yo-Sub Han, Kai Salomaa
2009 J jnl
On the descriptional complexity of Watson-Crick automata.
Theor. Comput. Sci.
Elena Czeizler, Eugen Czeizler, Lila Kari, Kai Salomaa
2009 J jnl
On the synchronized derivation depth of context-free grammars.
Theor. Comput. Sci.
Franziska Biegler, Kai Salomaa
2009 — conf
Operational State Complexity of Prefix-Free Regular Languages.
Automata, Formal Languages, and Related Topics
Yo-Sub Han, Kai Salomaa, Derick Wood
2009 J jnl
Operational state complexity of nested word automata.
Theor. Comput. Sci.
Xiaoxue Piao, Kai Salomaa
2009 C conf
State Complexity of Combined Operations for Prefix-Free Regular Languages.
LATA
Yo-Sub Han, Kai Salomaa, Sheng Yu
2009 C conf
State Complexity of Nested Word Automata.
LATA
Kai Salomaa
2009 J jnl
State complexity of basic operations on suffix-free regular languages.
Theor. Comput. Sci.
Yo-Sub Han, Kai Salomaa
2009 J jnl
State complexity of orthogonal catenation
CoRR
Mark Daley, Michael Domaratzki, Kai Salomaa
2009 J jnl
Variants of codes and indecomposable languages.
Inf. Comput.
Arto Salomaa, Kai Salomaa, Sheng Yu
2008 C conf
Language Decompositions, Primality, and Trajectory-Based Operations.
CIAA
Kai Salomaa
2008 C conf
Length Codes, Products of Languages and Primality.
LATA
Arto Salomaa, Kai Salomaa, Sheng Yu
2008 J jnl
Lower bounds for the transition complexity of NFAs.
J. Comput. Syst. Sci.
Michael Domaratzki, Kai Salomaa
2008 — conf
On the Synchronized Derivation Depth of Context-Free Grammars.
DCFS
Franziska Biegler, Kai Salomaa
2008 — conf
Operational State Complexity of Nested Word Automata.
DCFS
Xiaoxue Piao, Kai Salomaa
2008 J jnl
Preface.
Int. J. Found. Comput. Sci.
Michael Domaratzki, Kai Salomaa
2008 — conf
State Complexity of Orthogonal Catenation.
DCFS
Mark Daley, Michael Domaratzki, Kai Salomaa
2008 J jnl
State Complexity of Union and Intersection of Finite Languages.
Int. J. Found. Comput. Sci.
Yo-Sub Han, Kai Salomaa
2008 J jnl
The State Complexity of Two Combined Operations: Star of Catenation and Star of Reversal.
Fundam. Informaticae
Yuan Gao, Kai Salomaa, Sheng Yu
2008 — conf
Watson-Crick automata: determinism and state complexity.
DCFS
Elena Czeizler, Eugen Czeizler, Lila Kari, Kai Salomaa
2007 J jnl
An infinite hierarchy induced by depth synchronization.
Theor. Comput. Sci.
Franziska Biegler, Ian McQuillan, Kai Salomaa
2007 C conf
Descriptional Complexity of Nondeterministic Finite Automata.
Developments in Language Theory
Kai Salomaa
2007 C conf
Deterministic Caterpillar Expressions.
CIAA
Kai Salomaa, Sheng Yu, Jinfeng Zan
2007 J jnl
Intercode Regular Languages.
Fundam. Informaticae
Yo-Sub Han, Kai Salomaa, Derick Wood
2007 J jnl
On the State Complexity of Combined Operations and their Estimation.
Int. J. Found. Comput. Sci.
Kai Salomaa, Sheng Yu
2007 J jnl
On the existence of prime decompositions.
Theor. Comput. Sci.
Yo-Sub Han, Arto Salomaa, Kai Salomaa, Derick Wood, Sheng Yu
2007 J jnl
On the existence of regular approximations.
Theor. Comput. Sci.
Brendan J. Cordy, Kai Salomaa
2007 J jnl
State Complexity of Additive Weighted Finite Automata.
Int. J. Found. Comput. Sci.
Kai Salomaa, Paul N. Schofield
2007 B conf
State Complexity of Basic Operations on Suffix-Free Regular Languages.
MFCS
Yo-Sub Han, Kai Salomaa
2007 C conf
State Complexity of Union and Intersection of Finite Languages.
Developments in Language Theory
Yo-Sub Han, Kai Salomaa
2007 J jnl
State complexity of combined operations.
Theor. Comput. Sci.
Arto Salomaa, Kai Salomaa, Sheng Yu
2007 J jnl
Transition complexity of language operations.
Theor. Comput. Sci.
Michael Domaratzki, Kai Salomaa
2006 — conf
An Infinite Hierarchy Induced by Depth Synchronization.
DCFS
Franziska Biegler, Ian McQuillan, Kai Salomaa
2006 J jnl
Codes defined by multiple sets of trajectories.
Theor. Comput. Sci.
Michael Domaratzki, Kai Salomaa
2006 J jnl
Interpreted Trajectories.
Fundam. Informaticae
Michael Domaratzki, Grzegorz Rozenberg, Kai Salomaa
2006 Misc conf
Iterated TGR Languages: Membership Problem and Effective Closure Properties.
COCOON
Ian McQuillan, Kai Salomaa, Mark Daley
2006 B conf
Lower Bounds for the Transition Complexity of NFAs.
MFCS
Michael Domaratzki, Kai Salomaa
2006 C conf
Prime Decompositions of Regular Languages.
Developments in Language Theory
Yo-Sub Han, Kai Salomaa, Derick Wood
2006 — conf
Regular Approximations of Non-Regular Languages.
DCFS
Brendan J. Cordy, Kai Salomaa
2006 — conf
State Complexity of Catenation and Reversal Combined with Star.
DCFS
Yuan Gao, Kai Salomaa, Sheng Yu
2006 — conf
State Complexity of Prefix-Free Regular Languages.
DCFS
Yo-Sub Han, Kai Salomaa, Derick Wood
2006 — conf
Transition Complexity of Language Operations.
DCFS
Michael Domaratzki, Kai Salomaa
2005 J jnl
Contextual Grammars with Uniform Sets of Trajectories.
Fundam. Informaticae
Alexander Okhotin, Kai Salomaa
2005 J jnl
Decidability of trajectory-based equations.
Theor. Comput. Sci.
Michael Domaratzki, Kai Salomaa
2005 J jnl
Preface.
Int. J. Found. Comput. Sci.
Kai Salomaa, Sheng Yu
2005 J jnl
Restricted sets of trajectories and decidability of shuffle decompositions.
Int. J. Found. Comput. Sci.
Michael Domaratzki, Kai Salomaa
2004 B conf
Decidability of Trajectory-Based Equations.
MFCS
Michael Domaratzki, Kai Salomaa
2004 C ed.
Implementation and Application of Automata, 9th International Conference, CIAA 2004, Kingston, Canada, July 22-24, 2004, Revised Selected Papers
CIAA
Michael Domaratzki, Alexander Okhotin, Kai Salomaa, Sheng Yu
2004 — conf
Restricted sets of trajectories and decidability of shuffle decompositions.
DCFS
Michael Domaratzki, Kai Salomaa
2004 J jnl
State Complexity of Shuffle on Trajectories.
J. Autom. Lang. Comb.
Michael Domaratzki, Kai Salomaa
2004 — conf
Structural Equivalence of Regularly Extended E0L Grammars: An Automata Theoretic Proof.
Theory Is Forever
Kai Salomaa, Derick Wood
2003 J jnl
A Formal Study Of Practical Regular Expressions.
Int. J. Found. Comput. Sci.
Cezar Câmpeanu, Kai Salomaa, Sheng Yu
2002 J jnl
Additive Distances and Quasi-Distances Between Words.
J. Univers. Comput. Sci.
Cristian Calude, Kai Salomaa, Sheng Yu
2002 J jnl
Advances and Trends in Automata and Formal Languages A Collection of Papers in Honour of the 60th Birthday of Helmut Jürgensen - J.UCS Special Issue.
J. Univers. Comput. Sci.
Cristian Calude, Kai Salomaa, Sheng Yu
2002 J jnl
Decidability of EDT0L structural equivalence.
Theor. Comput. Sci.
Kai Salomaa, Sheng Yu
2002 J jnl
One-Visit Caterpillar Tree Automata.
Fundam. Informaticae
Alexander Okhotin, Kai Salomaa, Michael Domaratzki
2002 C conf
Regex and Extended Regex.
CIAA
Cezar Câmpeanu, Kai Salomaa, Sheng Yu
2002 J jnl
Shuffle Decompositions of Regular Languages.
Int. J. Found. Comput. Sci.
Cezar Câmpeanu, Kai Salomaa, Sándor Vágvölgyi
2002 — conf
State Complexity of Shuffle on Trajectories.
DCFS
Michael Domaratzki, Kai Salomaa
2002 J jnl
Tight Lower Bound for the State Complexity of Shuffle of Regular Languages.
J. Autom. Lang. Comb.
Cezar Câmpeanu, Kai Salomaa, Sheng Yu
2001 J jnl
A sharpening of the Parikh mapping.
RAIRO Theor. Informatics Appl.
Alexandru Mateescu, Arto Salomaa, Kai Salomaa, Sheng Yu
2001 J jnl
On the State Complexity of k-Entry Deterministic Finite Automata.
J. Autom. Lang. Comb.
Markus Holzer, Kai Salomaa, Sheng Yu
2001 C conf
Shuffle Quotient and Decompositions.
Developments in Language Theory
Cezar Câmpeanu, Kai Salomaa, Sándor Vágvölgyi
2000 J jnl
Alternating finite automata and star-free languages.
Theor. Comput. Sci.
Kai Salomaa, Sheng Yu
2000 J jnl
Efficient Implementation of Regular Languages Using Reversed Alternating Finite Automata.
Theor. Comput. Sci.
Kai Salomaa, Xiuming Wu, Sheng Yu
2000 J jnl
On Fairness of Many-Dimensional Trajectories.
J. Autom. Lang. Comb.
Alexandru Mateescu, Kai Salomaa, Sheng Yu
2000 — ch.
State Complexity of Regular Languages: Finite versus Infinite.
Finite Versus Infinite
Cezar Câmpeanu, Kai Salomaa, Sheng Yu
1999 J jnl
Generalized Fairness and Context-Free Languages.
Acta Cybern.
Kai Salomaa, Sheng Yu
1999 — conf
Metric Lexical Analysis.
WIA
Cristian Calude, Kai Salomaa, Sheng Yu
1999 — conf
State Complexity of Basic Operations on Finite Languages.
WIA
Cezar Câmpeanu, Karel Culík II, Kai Salomaa, Sheng Yu
1999 J jnl
Synchronization Expressions and Languages.
J. Univers. Comput. Sci.
Kai Salomaa, Sheng Yu
1999 — conf
Synchronization Expressions: Characterization Results and Implementation.
Jewels are Forever
Kai Salomaa, Sheng Yu
1998 — conf
Implementing Reversed Alternating Finite Automaton (r-AFA) Operations.
Workshop on Implementing Automata
Sandra Huerter, Kai Salomaa, Xiuming Wu, Sheng Yu
1998 J jnl
On the Size of Stack and Synchronization Alphabets of Tree Automata.
Fundam. Informaticae
George Rahonis, Kai Salomaa
1998 J jnl
Synchronization Expressions with Extended Join Operation.
Theor. Comput. Sci.
Kai Salomaa, Sheng Yu
1997 — conf
Block-Synchronization Context-Free Grammars.
Advances in Algorithms, Languages, and Complexity
Helmut Jürgensen, Kai Salomaa
1997 C conf
Decidability of fairness for context-free languages.
Developments in Language Theory
Alexandru Mateescu, Kai Salomaa, Sheng Yu
1997 — conf
Efficient Implementation of Regular Languages Using R-AFA.
Workshop on Implementing Automata
Kai Salomaa, Xiuming Wu, Sheng Yu
1997 C conf
Hierarchies of synchronized and algebraic forests.
Developments in Language Theory
George Rahonis, Kai Salomaa
1997 J jnl
NFA to DFA Transformation for Finite Languages over Arbitrary Alphabets.
J. Autom. Lang. Comb.
Kai Salomaa, Sheng Yu
1997 — conf
Rewriting Rules for Synchronization Languages.
Structures in Logic and Computer Science
Kai Salomaa, Sheng Yu
1997 J jnl
Semantics of Nonsequential Tree-Based Computation Schemes.
Fundam. Informaticae
Andrzej Ehrenfeucht, Grzegorz Rozenberg, Kai Salomaa
1996 J jnl
Decidability of Equivalence for Deterministic Synchronized Tree Automata.
Theor. Comput. Sci.
Kai Salomaa
1996 — conf
EDTOL Structural Equivalence is Decidable.
DMTCS
Kai Salomaa, Sheng Yu
1996 — conf
NFA to DFA Transformation for Finite Languages.
Workshop on Implementing Automata
Kai Salomaa, Sheng Yu
1996 J jnl
On Synchronization Languages.
Fundam. Informaticae
Lifu Guo, Kai Salomaa, Sheng Yu
1996 J jnl
On the Modularity of Decidability of Completeness and Termination.
J. Autom. Lang. Comb.
Kai Salomaa
1996 J jnl
Structural Equivalence and ET0L Grammars.
Theor. Comput. Sci.
Kai Salomaa, Derick Wood, Sheng Yu
1996 J jnl
Yield-Languages of Two-Way Pushdown Tree Automata.
Inf. Process. Lett.
Kai Salomaa
1995 J jnl
Complexity of E0L Structural Equivalence.
RAIRO Theor. Informatics Appl.
Kai Salomaa, Derick Wood, Sheng Yu
1995 — conf
Decidability of Equivalence for Deterministic Synchronized Tree Automata.
TAPSOFT
Kai Salomaa
1995 J jnl
Decision Problems for Patterns.
J. Comput. Syst. Sci.
Tao Jiang, Arto Salomaa, Kai Salomaa, Sheng Yu
1995 J jnl
Lexical Analysis with a Simple Finite-Fuzzy-Automaton Model.
J. Univers. Comput. Sci.
Alexandru Mateescu, Arto Salomaa, Kai Salomaa, Sheng Yu
1995 C conf
Nondeterminism Degrees for Context-Free Languages.
Developments in Language Theory
Kai Salomaa, Sheng Yu
1995 J jnl
P, NP and the Post Correspondence Problem
Inf. Comput.
Alexandru Mateescu, Arto Salomaa, Kai Salomaa, Sheng Yu
1994 B conf
Complexity of E0L Structural Equivalence.
MFCS
Kai Salomaa, Derick Wood, Sheng Yu
1994 J jnl
Measures of Nondeterminism for Pushdown Automata.
J. Comput. Syst. Sci.
Kai Salomaa, Sheng Yu
1994 J jnl
Pumping and Pushdown Machines.
RAIRO Theor. Informatics Appl.
Kai Salomaa, Derick Wood, Sheng Yu
1994 — conf
Rediscovering Pushdown Machines.
Results and Trends in Theoretical Computer Science
Kai Salomaa, Derick Wood, Sheng Yu
1994 J jnl
Semantics of Trees.
Math. Syst. Theory
Andrzej Ehrenfeucht, Grzegorz Rozenberg, Kai Salomaa
1994 — conf
Synchronization expressions and languages.
SPDP
Lifu Guo, Kai Salomaa, Sheng Yu
1994 J jnl
Synchronized Tree Automata.
Theor. Comput. Sci.
Kai Salomaa
1994 J jnl
The State Complexities of Some Basic Operations on Regular Languages.
Theor. Comput. Sci.
Sheng Yu, Qingyu Zhuang, Kai Salomaa
1994 J jnl
Transducers and the Decidability of Independence in Free Monoids.
Theor. Comput. Sci.
Helmut Jürgensen, Kai Salomaa, Sheng Yu
1993 J jnl
Decidability of the Intercode Property.
J. Inf. Process. Cybern.
Helmut Jürgensen, Kai Salomaa, Sheng Yu
1993 A* conf
Inclusion is Undecidable for Pattern Languages.
ICALP
Tao Jiang, Arto Salomaa, Kai Salomaa, Sheng Yu
1993 J jnl
Morphisms and rational tranducers.
Bull. EATCS
Kai Salomaa, Sheng Yu
1993 B conf
Structural Equivalences and ET0L Grammars (Extended Abstract).
FCT
Kai Salomaa, Derick Wood, Sheng Yu
1992 J jnl
Alternation Bounds for Tree Automata.
Acta Cybern.
Kai Salomaa
1992 J jnl
Confluence, ground confluence, and termination of monadic term rewriting systems.
J. Inf. Process. Cybern.
Kai Salomaa
1992 C conf
Obtaining Tight Upper Bounds for the State Complexities of DFA Operations.
ICCI
Sheng Yu, Qingyu Zhuang, Kai Salomaa
1991 — conf
Decidability of Confluence and Termination of Monadic Term Rewriting Systems.
RTA
Kai Salomaa
1991 J jnl
Decidability of Structural Equivalence of E0L Grammars.
Theor. Comput. Sci.
Kai Salomaa, Sheng Yu
1991 B conf
Degrees of Nondeterminism for Pushdown Automata.
FCT
Kai Salomaa, Sheng Yu
1991 J jnl
Primary Types of Instances of the Post Correspondence Problem.
Bull. EATCS
Arto Salomaa, Kai Salomaa, Sheng Yu
1990 J jnl
The Immortality Problem for LAG Systems.
Inf. Process. Lett.
Kai Salomaa, Sheng Yu
1989 B conf
Representation of Recursively Enumerable Languages Using Alternating Finite Tree Recognizers.
FCT
Kai Salomaa
1988 J jnl
Deterministic Tree Pushdown Automata and Monadic Tree Rewriting Systems.
J. Comput. Syst. Sci.
Kai Salomaa
1988 J jnl
Yield-Languages Recognized by Alternating Tree Recognizers.
RAIRO Theor. Informatics Appl.
Kai Salomaa
1986 — conf
Alternating Bottom-Up Tree Recognisers.
CAAP
Kai Salomaa
1984 J jnl
Direction Independent Context-Sensitive Grammars
Inf. Control.
H. C. M. Kleijn, Martti Penttonen, Grzegorz Rozenberg, Kai Salomaa
2023 — conf
Not What You've Signed Up For: Compromising Real-World LLM-Integrated Applications with Indirect Prompt Injection.
AISec
Kai Greshake, Sahar Abdelnabi, Shailesh Mishra, Christoph Endres, Thorsten Holz, Mario Fritz
2026 — preprint
CCX: Enabling Unmodified Intel SGX Applications on Arm CCA.
arXiv
Matti Schulze, Thorsten Holz, Felix C. Freiling