Tero Harju

Theor. Comput. Sci., 2024

A Note on Squares in Binary Words.

[BibT_eX]

[DOI]

Int. J. Found. Comput. Sci., 2024

Decision Problems on Copying and Shuffling.

[BibT_eX]

[DOI]

Fundam. Informaticae, 2024

2023

On bi-infinite and conjugate post correspondence problems.

[BibT_eX]

[DOI]

RAIRO Theor. Informatics Appl., 2023

Integer Weighted Automata on Infinite Words.

[BibT_eX]

[DOI]

Int. J. Found. Comput. Sci., 2023

2022

Avoiding square-free words on free groups.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2022

Critical factorisation in square-free words.

[BibT_eX]

[DOI]

RAIRO Theor. Informatics Appl., 2022

A recursive function coding number theoretic functions.

[BibT_eX]

[DOI]

Teemu Pirttimäki

CoRR, 2022

2021

Disposability in square-free words.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2021

The Conjugate Post Correspondence Problem.

[BibT_eX]

[DOI]

CoRR, 2021

Finite transducers and rational transductions.

[BibT_eX]

[DOI]

Proceedings of the Handbook of Automata Theory., 2021

2020

On Shuffling a Word with its Letter-to-Letter Substitution.

[BibT_eX]

[DOI]

Fundam. Informaticae, 2020

On the Steps of Emil Post: from Normal Systems to the Correspondence Decision Problem.

[BibT_eX]

[DOI]

Acta Cybern., 2020

2019

On square-free arithmetic progressions in infinite words.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2019

Some further results on squarefree arithmetic progressions in infinite words.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2019

2018

On fixed points of rational transductions.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2018

2017

Walks on tilings of polygons.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2017

Weighted automata on infinite words in the context of Attacker-Defender games.

[BibT_eX]

[DOI]

Inf. Comput., 2017

A New Proof for Undecidability of the Bi-Infinite Post Correspondence Problem.

[BibT_eX]

[DOI]

Fundam. Informaticae, 2017

2016

Abelian bordered factors and periodicity.

[BibT_eX]

[DOI]

Eur. J. Comb., 2016

2015

Square-free shuffles of words.

[BibT_eX]

[DOI]

Mike Müller

Theor. Comput. Sci., 2015

A note on short palindromes in square-free words.

[BibT_eX]

[DOI]

Mike Müller

Theor. Comput. Sci., 2015

On the n-permutation Post Correspondence Problem.

[BibT_eX]

[DOI]

Mari Ernvall

Theor. Comput. Sci., 2015

On generating binary words palindromically.

[BibT_eX]

[DOI]

Mari Huova

Luca Q. Zamboni

J. Comb. Theory A, 2015

2014

Tighter Undecidability Bounds for Matrix Mortality, Zero-in-the-Corner Problems, and More.

[BibT_eX]

[DOI]

CoRR, 2014

Minimal Similarity Relations for Square-Free Words.

[BibT_eX]

Proceedings of the Discrete Mathematics and Computer Science. In Memoriam Alexandru Mateescu (1952-2005)., 2014

2013

Composition and orbits of language operations: finiteness and upper bounds.

[BibT_eX]

[DOI]

Int. J. Comput. Math., 2013

New proof for the undecidability of the circular PCP.

[BibT_eX]

[DOI]

Acta Informatica, 2013

A Note on Square-Free Shuffles of Words.

[BibT_eX]

[DOI]

Proceedings of the Combinatorics on Words - 9th International Conference, 2013

2012

Computational Nature of Gene Assembly in Ciliates.

[BibT_eX]

[DOI]

Proceedings of the Handbook of Natural Computing, 2012

Square-free words obtained from prefixes by permutations.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2012

Pivots, determinants, and perfect matchings of graphs.

[BibT_eX]

[DOI]

Robert Brijder

Theor. Comput. Sci., 2012

Simple gene assembly as a rewriting of directed overlap-inclusion graphs.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2012

2011

On the number of frames in binary words.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2011

Directed Overlap-inclusion Graphs as Representations of Ciliate Genes.

[BibT_eX]

[DOI]

Fundam. Informaticae, 2011

A new proof for the decidability of D0L ultimate periodicity

[BibT_eX]

[DOI]

Proceedings of the Proceedings 8th International Conference Words 2011, 2011

Square-free Walks on Labelled Graphs

[BibT_eX]

[DOI]

CoRR, 2011

The Number of Positions Starting a Square in Binary Words.

[BibT_eX]

[DOI]

Electron. J. Comb., 2011

Finite Orbits of Language Operations.

[BibT_eX]

[DOI]

Proceedings of the Language and Automata Theory and Applications, 2011

2010

On the number of squares in partial words.

[BibT_eX]

[DOI]

RAIRO Theor. Informatics Appl., 2010

Cyclically repetition-free words on small alphabets.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2010

On the Periodicity of Morphic Words.

[BibT_eX]

[DOI]

Proceedings of the Developments in Language Theory, 14th International Conference, 2010

2009

Overlap-freeness in infinite partial words.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2009

The theorem of Fine and Wilf for relational periods.

[BibT_eX]

[DOI]

RAIRO Theor. Informatics Appl., 2009

Post Correspondence Problem and Small Dimensional Matrices.

[BibT_eX]

[DOI]

Proceedings of the Developments in Language Theory, 13th International Conference, 2009

On Involutions Arising from Graphs.

[BibT_eX]

[DOI]

Proceedings of the Algorithmic Bioprocesses, 2009

2008

Parallel complexity of signed graphs for gene assembly in ciliates.

[BibT_eX]

[DOI]

Chang Li

Soft Comput., 2008

Preface.

[BibT_eX]

[DOI]

Jean Berstel

RAIRO Theor. Informatics Appl., 2008

Square-free partial words.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2008

Post Correspondence Problem for short words.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2008

Preface.

[BibT_eX]

[DOI]

Int. J. Found. Comput. Sci., 2008

Matrix Equations and Hilbert's Tenth Problem.

[BibT_eX]

[DOI]

Int. J. Algebra Comput., 2008

Interaction Properties of Relational Periods.

[BibT_eX]

[DOI]

Discret. Math. Theor. Comput. Sci., 2008

Unbordered factors and Lyndon words.

[BibT_eX]

[DOI]

Jean-Pierre Duval

Discret. Math., 2008

Patterns of simple gene assembly in ciliates.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2008

Graph theoretic approach to parallel gene assembly.

[BibT_eX]

[DOI]

Chang Li

Discret. Appl. Math., 2008

Bordered Conjugates of Words over Large Alphabets.

[BibT_eX]

[DOI]

Electron. J. Comb., 2008

2007

Extension of the decidability of the marked PCP to instances with unique blocks.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2007

Relational codes of words.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2007

The Structure of Infinite Solutions of Marked and Binary Post Correspondence Problems.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2007

Periodicity and unbordered words: A proof of the extended duval conjecture.

[BibT_eX]

[DOI]

J. ACM, 2007

Undecidability Bounds for Integer Matrices Using Claus Instances.

[BibT_eX]

[DOI]

Int. J. Found. Comput. Sci., 2007

Towards a characterization of bipartite switching classes by means of forbidden subgraphs.

[BibT_eX]

[DOI]

Discuss. Math. Graph Theory, 2007

Finite metrics in switching classes.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2007

2006

On unique factorizations of primitive words.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2006

Parallelism in Gene Assembly.

[BibT_eX]

[DOI]

Nat. Comput., 2006

Undecidability of infinite post correspondence problem for instances of Size 9.

[BibT_eX]

[DOI]

RAIRO Theor. Informatics Appl., 2006

Undecidability in omega-Regular Languages.

[BibT_eX]

[DOI]

Fundam. Informaticae, 2006

The Embedding Problem for Switching Classes of Graphs.

[BibT_eX]

[DOI]

Fundam. Informaticae, 2006

Binary Words with Few Squares.

[BibT_eX]

Bull. EATCS, 2006

Positivity of second order linear recurrent sequences.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2006

Periods in Extensions of Words.

[BibT_eX]

[DOI]

Acta Informatica, 2006

Embedding linear orders in grids.

[BibT_eX]

[DOI]

Acta Informatica, 2006

Modelling Simple Operations for Gene Assembly.

[BibT_eX]

[DOI]

Proceedings of the Nanotechnology: Science and Computation, 2006

Complexity Measures for Gene Assembly.

[BibT_eX]

[DOI]

Proceedings of the Knowledge Discovery and Emergent Complexity in Bioinformatics, 2006

2005

Counting bordered and primitive words with a fixed weight.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2005

On the equation in a free semigroup.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2005

A characterization of periodicity of bi-infinite words.

[BibT_eX]

[DOI]

Arto Lepistö

Theor. Comput. Sci., 2005

Preface.

[BibT_eX]

[DOI]

Antonio Restivo

Theor. Comput. Sci., 2005

Equality sets for recursively enumerable languages.

[BibT_eX]

[DOI]

RAIRO Theor. Informatics Appl., 2005

Equality sets of prefix morphisms and regular star languages.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2005

Representation of Regular Languages by Equality Sets.

[BibT_eX]

Bull. EATCS, 2005

Characterizations of Regularity.

[BibT_eX]

[DOI]

Proceedings of the Finite-State Methods and Natural Language Processing, 2005

Simple Operations for Gene Assembly.

[BibT_eX]

[DOI]

Proceedings of the DNA Computing, 11th International Workshop on DNA Computing, 2005

Combinatorial Models of Gene Assembly.

[BibT_eX]

[DOI]

Proceedings of the New Computational Paradigms, 2005

2004

Many aspects of defect theorems.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2004

A Characterization of Acyclic Switching Classes of Graphs Using Forbidden Subgraphs.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2004

Border correlation of binary words.

[BibT_eX]

[DOI]

J. Comb. Theory A, 2004

Valence Languages Generated by Equality Sets.

[BibT_eX]

[DOI]

J. Autom. Lang. Comb., 2004

Minimal Duval Extensions.

[BibT_eX]

[DOI]

Int. J. Found. Comput. Sci., 2004

Gene Assembly in Celiates. Part I. Molecular Operations (Column: Natural Computing).

[BibT_eX]

Bull. EATCS, 2004

Transitivity of local complementation and switching on graphs.

[BibT_eX]

[DOI]

Discret. Math., 2004

Undecidability in matrices over Laurent polynomials.

[BibT_eX]

[DOI]

Adv. Appl. Math., 2004

Periodicity and Unbordered Words: A Proof of Duval?s Conjecture.

[BibT_eX]

[DOI]

Proceedings of the STACS 2004, 2004

Tutorial on DNA Computing and Graph Transformation.

[BibT_eX]

[DOI]

Proceedings of the Graph Transformations, Second International Conference, 2004

Embedding in Switching Classes with Skew Gains.

[BibT_eX]

[DOI]

Proceedings of the Graph Transformations, Second International Conference, 2004

Splicing Systems for Universal Turing Machines.

[BibT_eX]

[DOI]

Maurice Margenstern

Proceedings of the DNA Computing, 10th International Workshop on DNA Computing, 2004

Two Models for Gene Assembly in Ciliates.

[BibT_eX]

[DOI]

Proceedings of the Theory Is Forever, 2004

Formal Properties of Gene Assembly: Equivalence Problem for Overlap Graphs.

[BibT_eX]

[DOI]

Proceedings of the Aspects of Molecular Computing, 2004

2003

On the independence of equations in three variables.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2003

Formal systems for gene assembly in ciliates.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2003

Euler Graphs, Triangle-Free Graphs and Bipartite Graphs in Switching Classes.

[BibT_eX]

[DOI]

Emo Welzl

Fundam. Informaticae, 2003

Gene Assembly in Ciliates Part I. Molecular Operations.

[BibT_eX]

Bull. EATCS, 2003

Periodicity and Unbordered Segments of Words.

[BibT_eX]

Bull. EATCS, 2003

Decidability of the binary infinite Post Correspondence Problem.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2003

Languages Defined by Generalized Equality Sets.

[BibT_eX]

[DOI]

Proceedings of the Fundamentals of Computation Theory, 14th International Symposium, 2003

About Duval's Conjecture.

[BibT_eX]

[DOI]

Proceedings of the Developments in Language Theory, 7th International Conference, 2003

2002

Binary (generalized) Post Correspondence Problem.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2002

Gene assembly through cyclic graph decomposition.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2002

Characterizing the Micronuclear Gene Patterns in Ciliates.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2002

Some Decision Problems Concerning Semilinearity and Commutation.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2002

Density of Critical Factorizations.

[BibT_eX]

[DOI]

RAIRO Theor. Informatics Appl., 2002

Tutorial on DNA Computing and Graph Transformation - Computational Nature of Gene Assembly in Ciliates.

[BibT_eX]

[DOI]

Proceedings of the Graph Transformation, First International Conference, 2002

Computational Processes in Living Cells: Gene Assembly in Ciliates.

[BibT_eX]

[DOI]

Proceedings of the Developments in Language Theory, 6th International Conference, 2002

Infinite Solutions of Marked Post Correspondence Problem.

[BibT_eX]

[DOI]

Proceedings of the Formal and Natural Computing, 2002

2001

Mortality in Matrix Semigroups.

[BibT_eX]

[DOI]

Am. Math. Mon., 2001

Some New Results on Post Correspondence Problem and Its Modifications.

[BibT_eX]

Bull. EATCS, 2001

Decision Questions Concerning Semilinearity, Morphisms, and Commutation of Languages.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 28th International Colloquium, 2001

Patterns of Micronuclear Genes in ciliates.

[BibT_eX]

[DOI]

Proceedings of the DNA Computing, 7th International Workshop on DNA-Based Computers, 2001

Decision Questions on Integer Matrices.

[BibT_eX]

[DOI]

Proceedings of the Developments in Language Theory, 5th International Conference, 2001

An Undecidability Result Concerning Periodic Morphisms.

[BibT_eX]

[DOI]

Proceedings of the Developments in Language Theory, 5th International Conference, 2001

Forbidden subsequences and permutations sortable on two parallel stacks.

[BibT_eX]

Proceedings of the Where Mathematics, 2001

2000

Periods and Binary Words.

[BibT_eX]

[DOI]

J. Comb. Theory A, 2000

Pancyclicity in switching classes.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2000

Generalized Post Correspondence Problem for Marked Morphisms.

[BibT_eX]

[DOI]

Int. J. Algebra Comput., 2000

The size of switching classes with skew gains.

[BibT_eX]

[DOI]

Discret. Math., 2000

1999

Undecidability of the equivalence of finite substitutions on regular language.

[BibT_eX]

[DOI]

RAIRO Theor. Informatics Appl., 1999

On the Undecidability of Freeness of Matrix Semigroups.

[BibT_eX]

[DOI]

Julien Cassaigne

Int. J. Algebra Comput., 1999

Undecidability in Integer Weighted Finite Automata.

[BibT_eX]

[DOI]

Fundam. Informaticae, 1999

Generalized PCP Is Decidable for Marked Morphisms.

[BibT_eX]

[DOI]

Proceedings of the Fundamentals of Computation Theory, 12th International Symposium, 1999

Languages Accepted by Integer Weighted Finite Automata.

[BibT_eX]

Proceedings of the Jewels are Forever, 1999

The Theory of 2-Structures - A Framework for Decomposition and Transformation of Graphs.

[BibT_eX]

[DOI]

World Scientific, ISBN: 978-981-02-4042-4, 1999

1998

On Quasi Orders of Words and the Confluence Property.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1998

Acyclicity of Switching Classes.

[BibT_eX]

[DOI]

Eur. J. Comb., 1998

Permutations, parenthesis words, and Schröder numbers.

[BibT_eX]

[DOI]

Discret. Math., 1998

Complexity Issues in Switching of Graphs.

[BibT_eX]

[DOI]

Proceedings of the Theory and Application of Graph Transformations, 1998

Shuffle on Trajectories: The Schützenberger Product and Related Operations.

[BibT_eX]

[DOI]

Alexandru Mateescu

Arto Salomaa

Proceedings of the Mathematical Foundations of Computer Science 1998, 1998

1997

Morphisms.

[BibT_eX]

[DOI]

Proceedings of the Handbook of Formal Languages, Volume 1: Word, Language, Grammar., 1997

A Note on Decidability Questions on Presentations of Word Semigroups.

[BibT_eX]

[DOI]

Christian Choffrut

Theor. Comput. Sci., 1997

Invariants of Inversive 2-Structures on Groups of Labels.

[BibT_eX]

[DOI]

Math. Struct. Comput. Sci., 1997

Languages Obtained from Infinite Words.

[BibT_eX]

[DOI]

RAIRO Theor. Informatics Appl., 1997

On a Geometric Problem of Zigzags.

[BibT_eX]

[DOI]

Inf. Process. Lett., 1997

Compactness of Systems of Equations in Semigroups.

[BibT_eX]

[DOI]

Wojciech Plandowski

Int. J. Algebra Comput., 1997

2-Structures - A Framework For Decomposition And Transformation Of Graphs.

[BibT_eX]

Proceedings of the Handbook of Graph Grammars and Computing by Graph Transformations, 1997

Compactness of Systems of Equations on Completely Regular Semigroups.

[BibT_eX]

[DOI]

Mario Petrich

Proceedings of the Structures in Logic and Computer Science, 1997

1996

Flatwords and Post Correspondence Problem.

[BibT_eX]

[DOI]

Marjo Lipponen

Alexandru Mateescu

Theor. Comput. Sci., 1996

Characterization and Complexity of Uniformly Non Primitive Labeled 2-Structures.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1996

Remarks on Generalized Post Correspondence Problem.

[BibT_eX]

[DOI]

Daniel Krob

Proceedings of the STACS 96, 1996

1995

Theory of 2-Structures.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 22nd International Colloquium, 1995

1994

Representation of Rational Functions with Prefix and Suffix Codings.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1994

The Intersection Problem for Alphabetic Vector Monoids.

[BibT_eX]

[DOI]

N. W. Keesmaat

RAIRO Theor. Informatics Appl., 1994

Reductions for Primitive 2-Structures.

[BibT_eX]

[DOI]

Fundam. Informaticae, 1994

Incremental construction of 2-structures.

[BibT_eX]

[DOI]

Discret. Math., 1994

Group Based Graph Transformations and Hierarchical Representations of Graphs.

[BibT_eX]

[DOI]

Proceedings of the Graph Gramars and Their Application to Computer Science, 1994

Decompostion of Infinite Labeled 2-Structures.

[BibT_eX]

[DOI]

Proceedings of the Results and Trends in Theoretical Computer Science, 1994

Identities and Transductions.

[BibT_eX]

[DOI]

Proceedings of the Results and Trends in Theoretical Computer Science, 1994

1993

Morphisms and rational tranducers.

[BibT_eX]

Bull. EATCS, 1993

1992

Compositional representation of rational functions.

[BibT_eX]

[DOI]

RAIRO Theor. Informatics Appl., 1992

Deterministic Sequential Functions.

[BibT_eX]

[DOI]

Acta Informatica, 1992

1991

The Equivalence Problem of Multitape Finite Automata.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1991

Decidability problems for unary output sequential transducers.

[BibT_eX]

[DOI]

Discret. Appl. Math., 1991

Splicing semigroups of dominoes and DNA.

[BibT_eX]

[DOI]

Discret. Appl. Math., 1991

1990

Decidability of the Multiplicity Equivalence of Multitape Finite Automata

[BibT_eX]

[DOI]

Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, 1990

1989

Cardinality Problems of Composition of Morphisms and Inverse Morphisms.

[BibT_eX]

[DOI]

Math. Syst. Theory, 1989

Dominoes and the Regularity of DNS Splicing Languages.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 16th International Colloquium, 1989

1986

On the Periodicity of Morphisms on Free Monoids.

[BibT_eX]

[DOI]

Matti Linna

RAIRO Theor. Informatics Appl., 1986

On morphic generation of regular languages.

[BibT_eX]

[DOI]

Discret. Appl. Math., 1986

1984

The Equations h(w)=w-n in Binary Alphabets.

[BibT_eX]

[DOI]

Matti Linna

Theor. Comput. Sci., 1984

The omega-Sequence Problem for DOL Systems Is Decidable.

[BibT_eX]

[DOI]

J. ACM, 1984

1982

Dominoes Over a Free Monoid.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1982

1981

The omega-Sequence Equivalence Problem for DOL Systems Is Decidable

[BibT_eX]

[DOI]

Proceedings of the 13th Annual ACM Symposium on Theory of Computing, 1981

1979

A Simulation Result for the Auxiliary Pushdown Automata.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1979

1977

A Polynomial Recognition Algorithm for the EDTOL Languages.

[BibT_eX]